Active questions tagged genetic-algorithms - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-22T00:15:39Z https://cs.stackexchange.com/feeds/tag/genetic-algorithms https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/89391 0 Using 2-opt Heuristic in a Genetic Algorithm for TSP Haytam https://cs.stackexchange.com/users/85705 2018-03-15T22:57:41Z 2019-09-03T18:02:55Z <p>I read few papers while trying to find some better approachs to solve the TSP (Traveling salesman problem) as close to the optimal solution as possible. I implemented a Improved Greedy Crossover (<a href="https://arxiv.org/ftp/arxiv/papers/1209/1209.5339.pdf" rel="nofollow noreferrer">https://arxiv.org/ftp/arxiv/papers/1209/1209.5339.pdf</a>) and I saw in the same paper that he uses the 2-opt heuristic (and the 3-opt one) on every new child, so I went ahead and did the same.</p> <p>Using this definition of the 2-opt (<a href="https://en.wikipedia.org/wiki/2-opt" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/2-opt</a>) I implemented their following pseudo-code:</p> <pre><code> repeat until no improvement is made { start_again: best_distance = calculateTotalDistance(existing_route) for (i = 1; i &lt; number of nodes eligible to be swapped - 1; i++) { for (k = i + 1; k &lt; number of nodes eligible to be swapped; k++) { new_route = 2optSwap(existing_route, i, k) new_distance = calculateTotalDistance(new_route) if (new_distance &lt; best_distance) { existing_route = new_route goto start_again } } } } </code></pre> <p>The problem with my class is that it takes way too much time when tested on a 51 cities instance (not to mention that 1 generation takes more than 20 minutes in the a280 instance)..</p> <p>Is there a better approach to this algorithm? A faster/more robust way of improving the new children?</p> https://cs.stackexchange.com/q/93556 1 Choosing Fitness function for float output in Genetic algorithm Max Z https://cs.stackexchange.com/users/89941 2018-06-26T19:46:04Z 2019-08-21T01:02:45Z <p>I have a NN that has ten outputs. The output values range between 0 and 1. The elements in the target array are all zeros except one element, which is "one".</p> <p>I am searching for a Fitness Function that will correctly evaluate (score) the Neural Networks.</p> <p>Currently, I am trying to calculate the distance between the target and the output arrays. The issue is that at the beginning all my NNs return results that are very close to each other and I can't properly choose the fittest individuals. </p> <p>For Example:</p> <pre><code>NN1 -&gt; FF score:0.10030096 -&gt; Rank? NN2 -&gt; FF score:0.09996143 -&gt; Rank? NN3 -&gt; FF score:0.10015215 -&gt; Rank? </code></pre> <p>Any suggestions?</p> https://cs.stackexchange.com/q/112603 0 Number of Times to Run an Evolutionary (Genetic) Algorithm compbiostats https://cs.stackexchange.com/users/97228 2019-08-09T14:45:49Z 2019-08-09T14:45:49Z <p>Evolutionary algorithms like genetic algorithms (GAs) are typically run multiple times and the outputted results are averaged across successive runs. </p> <p>However, in the case of long-runtime algorithms (e.g., due to large population sizes or algorithm complexity), is there any justification for running GAs (and the like) only once? Clearly, statistical evaluation of variability is not possible in such a case.</p> <p>I've not been able to find anything in the literature on the subject, so am asking here to gain some insight from the CS community. </p> https://cs.stackexchange.com/q/111585 0 Is this a good way of generating diverse solutions to a problem using a genetic algorithm? John Salter https://cs.stackexchange.com/users/107331 2019-07-07T13:49:24Z 2019-08-06T19:03:40Z <p>Imagine a complicated blackbox-esque system that has 20 inputs and 5 outputs. I have a set of criteria I am able to use to construct a fitness function. I run a genetic algorithm to deduce values which maximize my fitness function, and I keep iterating until a solution emerges which passes a threshold. Once this threshold is met, the genetic algorithm starts afresh except the fitness function now includes a positive term proportional to the euclidan distance between the candidate solutions and the previously determined solution (the one that exceeded the threshold earliar.) </p> <p>Once a second set of inputs is found which matches exceeds the threshold, the fitness function is updated to also include a term proportional to the euclidian disance from the second solution. Both terms are divided by two to prevent this euclidan distance derived terms in my fitness function from overpowering the others.</p> <p>Would a process like this, iterated sufficiently, be an efficient way of generating a diverse set of inputs, each of which represents a set of inputs which achieve a high fitness score?</p> <p>(Please assume that a diverse of solutions exists for the problem at hand; the goal of the algorithm is to find them)</p> https://cs.stackexchange.com/q/112398 1 The solution to my wind farm layout optimization using GA produces different results every time i run it. Is their a way to curb it? [closed] NARENDER REDDY https://cs.stackexchange.com/users/108177 2019-08-02T16:59:12Z 2019-08-02T16:59:12Z <p>Each layout consists of 1000 turbines or more and is ranked based on power produced.<br> The way my algorithm works is:-</p> <pre><code>&gt;&gt;Initial parents created(2 layouts) &gt;&gt;Crossover and Mutation of Initial Parents and population is created &gt;&gt;Calculation of power produced by each layout &gt;&gt;Sorting of layouts using power values &gt;&gt;Top 2 layouts producing max power selected for next generation &gt;&gt;The steps are repeated till termination criteria is reached </code></pre> <p>each time I run the algorithm, I get a different configuration of layout. Can anyone help me out in reducing the ambiguity in the output?</p> https://cs.stackexchange.com/q/111781 1 Genetic programming - tournament selection and elite GuyT https://cs.stackexchange.com/users/107529 2019-07-13T12:05:59Z 2019-07-13T12:05:59Z <p>I am writing a thesis about automatic GUI testing. In order to find the fittest strategy I am using GP. I am using tournament selection to select chromosomes for the next generation and elitism to make sure the strongest elite(s) will proceed to the next round.</p> <p>Basically, I have 2 questions:</p> <p>a) Many papers use 7 as tournament size because this is the default in one of Koza's papers. From my understanding we are missing the point of Koza. I think 7 <em>might have been</em> a good fit for his research, which may be based on his population. Shouldn't we use the probability and adjust the tournament size accordingly instead? As one may already have noticed, I am making assumptions. Are there papers I may have missed that are writing about choosing the right tournament size? If not, should experiments be conducted to find the right tournament size for a specific research setup?</p> <p>Eg. Following results in a probability of 7% that a chromosome is part of the tournament. </p> <p>Population: 100 Elites: 5 Tournament selection: 7</p> <p>Increasing the tournament size (selection pressure) will result in a higher probability a chromosome will be selected for the tournament. </p> <p>b) If I have a population of 100, a tournament size of 10 and 5 elites, if I understand correctly, 6 chromosomes will make it to the next generation right? </p> <p>Please people, enlighten me :)</p> https://cs.stackexchange.com/q/91649 3 Difference between selecting a large pool of individuals for reproduction, and selecting two parents specifically Nick Thissen https://cs.stackexchange.com/users/88234 2018-05-08T11:06:22Z 2019-07-12T13:02:40Z <p>I have implemented a genetic algorithm for an optimization problem and I'm now trying to improve it to see if I can find better solutions or faster convergence.</p> <p>I am confused about the <em>selection</em> part of the algorithm and how it relates to <em>selecting parents for cross-over</em>. In my mind these things are <strong>not</strong> the same yet many resources seem to treat them the same, and I can't figure out how or why.</p> <p>As far as I understand the terms:</p> <ol> <li><p><strong>Selection</strong> means: selecting a subset of the current population (e.g. half) which will reproduce to form the new generation. Non-selected individuals are discarded. Selection should be based on fitness in some way such that more fit individuals are selected with higher probability (but bad individuals can still be selected for sufficient genetic diversity).</p></li> <li><p><strong>Selecting parents for cross-over</strong> means: from the group of selected individuals, take <em>two</em> parents to cross-over and form <em>one</em> child. (I know schemes are possible with more than two parents and/or more than one children but let's keep it simple). This step should be repeated until I filled the new population.</p></li> </ol> <p>Let's say I have a population of 50 and <strong>select</strong> half of them, leaving me with 25 parents which will now reproduce to form 50 new individuals. Since there are only 25 parents and I need 50 children, probability is high that one parent can have multiple children. There is of course a chance that the same parent reproduces with itself giving an identical copy (ignoring mutation for now).</p> <p>My point here is that the two concepts are not the same. In <strong>1</strong> I select many individuals that will <em>later</em> reproduce, but for now I am merely letting the non-selected individuals die. In <strong>2</strong> I then select <em>two</em> parents specifically to cross-over and form one new individual. It is entirely possible (though obviously very unlikely) that I keep selecting the same 2 parents from my pool 25 and ignore the others.</p> <p>I know of various selection operators but I am confused about which is applied to which scenario. For example:</p> <ul> <li><p>Tournament selection: grab a few (e.g. 2 or 4) individuals at random, and then take the best. This gives me just <em>one</em> individual. I can use this 25 times to select the 25 individuals (<strong>1</strong>), or I can use this twice on the group of selected individuals to select two parents for reproduction (<strong>2</strong>). Which one is it?</p></li> <li><p>Roulette wheel or fitness proportionate selection: grab an individual at random but with probability based on their fitness. Again: I can use this 25 times to form my pool of selected individuals, or I can use it just twice on that subset of individuals to select the two parents. Which one?</p></li> <li><p>Stochastic universal sampling (SUS): sample several individuals at equally spaced intervals based on fitness. Here it seems clear I am selecting <em>multiple</em> individuals at once (though I suppose it could be "2"), so it seems likely this can be used to form my pool of 25 individuals. </p></li> <li><p>Truncation: simply take the best x% and discard the rest (I know this isn't good for genetic diversity). Clearly this can be used to select the pool of 25 individuals (e.g. discard the worst 25) but how do I now proceed to select two parents?</p></li> </ul> <p>In general I can apply all of these selection operators to select a large group of individuals, but then I still don't know how to select (from that subset) two parents to reproduce. Is this secondary selection just random? Or should I take fitness into account again here (seems counterproductive, I already selected on fitness previously)? Or should I make sure every parent is equally selected?</p> https://cs.stackexchange.com/q/111029 0 How can I write a genetic programming algorithm, given that the Halting problem is unsolvable? olinarr https://cs.stackexchange.com/users/97611 2019-06-21T16:03:43Z 2019-06-22T07:30:29Z <p>I am learning genetic programming and to practice I want to write a simple algorithm which evolves a program that solves a simple function (say, square root). I intend to represent programs as abstract syntax trees.</p> <p>However, one of the functors is the while loop. Of course, in assesting a tree's fitness, I have to evaluate the program: but the halting problem is unsolvable. How can I tell if a given tree stops? Of course I can't, so what are some practicals ways to approach this problem?</p> <p>Should I make my simple tree-language not turing complete? Or maybe give a timeout to each tree?</p> https://cs.stackexchange.com/q/110001 1 How to improve convergence to an equilibrium value, & damp oscillation? Rosie F https://cs.stackexchange.com/users/78436 2019-05-29T10:34:22Z 2019-05-29T10:34:22Z <p>I am developing a program which seeks strategies for the players A, B in any of a family of simple 2-player gambling-games. The program iterates, using a genetic algorithm to determine, from the current iteration's results, the strategies which are to play one another in the next iteration.</p> <p>Below I give an overview of my algorithm. Although I've used pseudocode, I am <em>not</em> asking about how to <em>code</em> an algorithm; rather, I would like to learn what the <em>algorithm</em> should contain.</p> <pre><code>main { Strategy A[], B[]; input nIters, nStrats, maxTweak, gameRules; A := nStrats random strategies; B := nStrats random strategies; for(t=1..nIters) { make each A play each B; for each A and each B its total score := sum of its scores in its individual games; sort the A's by total score; sort the B's by total score; v := the game's bias in favour of the best A; write v; evolveStrategies(A, nStrats, maxTweak); evolveStrategies(B, nStrats, maxTweak); } } evolveStrategies(X, nStrats, maxTweak) { keep the best few Xs where they are; for(each of the others X[i]) { j := index of one of the best Xs; X[i] := X[j]; tweak the value of each parameter of X[i] by no more than maxTweak; } } </code></pre> <p>The nature of the game is that there is (with best play by A and B) a bias (positive or negative) in favour of A. Its value <span class="math-container">$V$</span> is what it is when A's and B's strategies are those at a Nash equilibrium. Let <span class="math-container">$v$</span> be my program's estimate of <span class="math-container">$V$</span>. Ideally my iterations' successive values of <span class="math-container">$v$</span> would converge to <span class="math-container">$V$</span>. For some games in the relevant family, I happen to know what <span class="math-container">$V$</span> is; for others, I don't.</p> <p>The trouble I find is that even if maxTweak is very small, the succession of <span class="math-container">$v$</span>-values written shows oscillation with an amplitude much larger than maxTweak. Choosing a suitably large number of iterations shows that the oscillation, after an initial large rise and fall, is hardly damped if at all. For example on a simple game, maxTweak=<span class="math-container">$4\times10^{-6}$</span> gives an initial large rise and fall, then oscillation with amplitude, peak to peak, <span class="math-container">$\approx 0.2$</span> and period <span class="math-container">$\approx 500000$</span> iterations.</p> <p>One solution is to reduce maxTweak. But this entails using many more iterations, and thus more CPU time. A more radical change to my approach is needed.</p> <p>Given that, a priori, the program does not know the oscillation's period or the limit value, how can my program detect the oscillation and deal with it (e.g. damp it)?</p> <p>If <span class="math-container">$v$</span> varied as undamped simple harmonic motion, plus a constant, then <span class="math-container">$\frac{dv}{dt}$</span> varies as undamped simple harmonic motion about 0, so <span class="math-container">$\frac{d^3 v}{dt^3} \propto -\frac{dv}{dt}$</span>. Since the tweaking is random, there will be small-scale oscillations due to that, as well as the larger-scale oscillation. So it seems that attempts to find higher-order derivatives of <span class="math-container">$v$</span> as a function of <span class="math-container">$t$</span> will fail.</p> <p>I tried estimating the first and second derivatives <span class="math-container">$\frac{dv}{dt}$</span> and <span class="math-container">$\frac{d^2 v}{dt^2}$</span> by maintaining exponentially-weighted averages of <span class="math-container">$v$</span> and my estimate of <span class="math-container">$\frac{dv}{dt}$</span>. Based on the sign of my estimate of <span class="math-container">$\frac{d^2 v}{dt^2}$</span> I evolved just A or B. This increased the number of iterations during <span class="math-container">$v$</span>'s initial large rise and fall, but the following oscillation was as large and undamped as before.</p> <p>One idea is to start maxTweak at a value which is not small, and adaptively reduce it. But in deciding (at each iteration) whether to reduce it or not, what should I be looking for?</p> https://cs.stackexchange.com/q/27625 22 Why do low fitness individuals have a chance to survive to the next generation? Max https://cs.stackexchange.com/users/19332 2014-06-12T15:49:19Z 2019-05-27T12:01:02Z <p>I am currently reading and watching about genetic algorithm and I find it very interesting (I haven't had the chance to study it while I was at the university).</p> <p>I understand that mutations are based on probability (randomness is the root of evolution) but I don't get why survival is.</p> <p>From what I understand, an individual $I$ having a fitness $F(i)$ such as for another individual $J$ having a fitness $F(j)$ we have $F(i) &gt; F(j)$, then $I$ has a better probability than $J$ to survive to the next generation.</p> <p>Probability implies that $J$ <em>may</em> survive and $I$ <em>may</em> not (with "bad luck"). I don't understand why this is good at all? If $I$ would <strong>always</strong> survive the selection, what would go wrong in the algorithm? My guess is that the algorithm would be similar to a greedy algorithm but I am not sure.</p> https://cs.stackexchange.com/q/109786 0 What kind of standard deviation must be used in optimization algorithms? kylo https://cs.stackexchange.com/users/105733 2019-05-23T23:22:35Z 2019-05-24T07:09:13Z <p>I would like to ask about the standard deviation of objective function value. </p> <p>There are two types of standard deviations:</p> <ol> <li><p>Population standard deviation</p></li> <li><p>Sample standard deviation</p></li> </ol> <p>In metaheuristic optimization algorithms most scholars are used std in your papers. What kind of standard deviation is used in metaheuristic optimization algorithms?</p> https://cs.stackexchange.com/q/103720 -1 Genetic algorithm problem Ahmed Cheikh https://cs.stackexchange.com/users/99842 2019-02-01T14:21:23Z 2019-02-01T23:46:06Z <p>This is a problem I found in an old exam in my school. I have to solve this Genetic Algorithm problem:<br> N students <span class="math-container">$x_{1},..,x_{N}$</span> have answered a quiz of 10 questions (True or False questions) and have obtained scors <span class="math-container">$s_{1},..,s_{N}$</span> (score can go from 0 to 10).<br/> From these scores we would likw to deduce what are the correct answers to each question.<br/> I don't know where to start. For my population it is obvious that it is the set of list of 10 booleans. <br/> But for my fitness I don't what to choose since we don't have a rule to calculate score and we don't have the target (correct answers: we are trying to find)</p> <p>Do you guys have any idea on how to solve this?</p> https://cs.stackexchange.com/q/103650 0 Crossover topologically identical neural networks nc404 https://cs.stackexchange.com/users/99755 2019-01-30T23:31:31Z 2019-01-31T00:03:36Z <p>I have recently learned about artificial neural networks (very interesting) and genetic algorithms (also very interesting). I have read some suggestions concerning how to crossover two parent neural networks to produce a child. For example, randomly selecting weights and biases from either one parent or the other, or selecting the first L layers from one parent and the rest from the other. I was wondering if taking the average weights and biases (such that w<sub>ij</sub><sup>(L)</sup> of the child networks equals the average w<sub>ij</sub><sup>(L)</sup> of the parents, and similarly for b<sub>i</sub><sup>(L)</sup>) would be a proper crossover operation.</p> <p>Which of these operations would be best suited for most genetic algorithms involving neural networks? Note that I want to limit the scope of this question only to topologically identical parents producing a child with that same topology.</p> https://cs.stackexchange.com/q/103109 1 Shortest common supersequence with Genetic Algorithm nrofis https://cs.stackexchange.com/users/42150 2019-01-19T20:57:15Z 2019-01-20T09:02:36Z <p>I'm trying to solve the shortest common supersequence with Genetic Algorithm. I found it a little bit hard to reduce the size of the chromosomes in each generation.</p> <p>I know that the maximum size of the chromosome is the total length of the strings. Even if we create a "naive" genetic algorithm: Totally random strings (with different length) as initial population, mutation that replace a character, fitness that return how much strings that chromosome contains etc. How the crossover can reduce the size of the chromosome length? If we choose n-points crossover, the length of the children cannot be smaller than the shorter parent.</p> <p>So how genetic algorithm can solve such problems that need the shortest chromosome length? How crossover can reduce the chromosome length?</p> https://cs.stackexchange.com/q/40714 0 Looking for an algorithm to generate an identicon/avatar from genome data Andrew Munro https://cs.stackexchange.com/users/30014 2015-03-24T20:34:06Z 2019-01-10T11:51:14Z <p>I am looking to develop an app that generates a single identicon image that summarizes the genome information in visual form. </p> <p>Identicons are essentially a visual hash of of data. usually string data such as an IP address or name. In this case, rather than generating an identicon from a single piece of string data. I want to use the entirety of the genotype information (the 4th column) to summarize this data into a graphical representation as a way to visually identify someone from their partial genome. </p> <p>The input file is a tab-separated file consisting of 600,000 rows. Each row contains the chromosome identifier (There are 23 in total: 1-20, X, Y or MT), the position of the single nucleotide polymorphism (SNP) and the genotype (a two character variation of G,A,T or C). Below is a two line excerpt from the file.</p> <pre><code>#RSID Chromosome Position Genotype rs7537756 1 854250 AG rs13302982 1 861808 GG </code></pre> <p>Using the Chromasome, Position and Genotype columns. I would like to generate an abstract identifying image from this data. Since there is far too much data, this image does not need to capture the data, only summarize it in a visual fashion. The goal is to setup a service that analyzes anyone's genome file and generates an identicon that is unique to them.</p> <p>For more information on identicons <a href="http://en.wikipedia.org/wiki/Identicon" rel="nofollow" title="Wiki Page">See the wiki page</a></p> https://cs.stackexchange.com/q/99187 1 genetic algorithm with different categories of parameters Alasmari https://cs.stackexchange.com/users/95633 2018-10-27T22:28:44Z 2018-10-28T01:25:30Z <p>I am trying to use a genetic algorithm to solve a problem. However, I find it difficult to represent the chromosomes in my problem. In the problem, I have two categories of parameters, and each gene inside the chromosome has a specific range of values.</p> <p>For example, Category <span class="math-container">$A$</span> has chromosome <span class="math-container">$X$</span> that has the following genes: <span class="math-container">$x_1$</span>, <span class="math-container">$x_2$</span>, <span class="math-container">$x_3$</span>, <span class="math-container">$x_4$</span>, where</p> <p><span class="math-container">$x_1$</span> takes value between <span class="math-container">$1$</span> and <span class="math-container">$5$</span> (inclusive).</p> <p><span class="math-container">$x_2$</span> takes value between <span class="math-container">$10$</span> and <span class="math-container">$30$</span> (inclusive).</p> <p><span class="math-container">$x_3$</span> takes value in the set <span class="math-container">$\{1,4,6,10\}$</span>.</p> <p>Also, Category <span class="math-container">$B$</span> has chromosome <span class="math-container">$Y$</span> that have genes with different values.</p> <p>The difficulty here is how can I encode the chromosomes <span class="math-container">$X$</span> and <span class="math-container">$Y$</span> with the different ranges of values?</p> https://cs.stackexchange.com/q/95919 1 Generate a random tree population Lorenz https://cs.stackexchange.com/users/92304 2018-08-03T13:42:43Z 2018-08-03T14:48:56Z <p>Given</p> <ul> <li>a unbalanced k-ary tree <code>base</code> (with internal nodes that represent operators and leafs representing values) from the space of all unbalanced k-ary trees <code>T</code></li> <li>a distance function <code>delta(t, t') = number of edit operations to transform t into t'</code></li> <li>the edit operations <code>add(t)</code> (adding a random leaf), <code>remove(t)</code> (removing a random subtree), <code>relabel(t)</code> (relabel a random node) <code>merge(t, t')</code> (merge <code>t</code> and <code>t'</code>)</li> </ul> <blockquote>For a genetic algorithm I need to generate a population of <code>n</code> trees that are not more than <code>k</code> edit operations away from <code>base</code>. I must prove that any tree within this space has equal propablity to be generated and that any tree can be generated.</blockquote> <p>The only idea I can think of was:</p> <ol> <li><p>draw a random number <code>l</code> within <code>[0, k]</code></p></li> <li><p>define a random sequence <code>seq</code> of size <code>l</code> edit operations </p></li> <li><p>apply <code>seq</code> to <code>base</code></p></li> </ol> <p>This aproach though does not garanty that any tree less than k away from base is generated?!</p> <p>//EDIT</p> <p>My other approach:</p> <ol> <li><p>Generate a random tree <code>rt</code></p></li> <li><p>Measure distance <code>d</code> and calculate <code>seq</code> the optimal set of edit operations beween <code>rt</code> and <code>base</code></p></li> <li><p>apply <code>[k-d, d]</code> edit operations to <code>rt</code></p></li> </ol> <p>I am not shure if in that way any tree can be generated with the same propability.</p> https://cs.stackexchange.com/q/90228 0 Crossover operator in genetic algorithms in Neural Networks Lam Nguyen https://cs.stackexchange.com/users/86757 2018-04-04T21:47:38Z 2018-06-11T18:23:32Z <p>I am developing a neural network that is trained using a genetic algorithm. The neural network is a multilayer perceptron using $\tanh$ as its activation function. Currently, the genotype of the neural network is by its weights. I used the method of making a connectivity matrix and linearizing it according to this paper: <a href="http://sci2s.ugr.es/keel/pdf/keel/articulo/NN-Garcia05.pdf" rel="nofollow noreferrer">http://sci2s.ugr.es/keel/pdf/keel/articulo/NN-Garcia05.pdf</a></p> <p>What is a good crossover method for this? I've tried uniform crossover but it is too disruptive as there is no improvement whatsoever. Single-point crossover is discouraged as I have read, so what should I use?</p> https://cs.stackexchange.com/q/91833 0 Evolutionary algorithm - is there a relation between minimum iterations and size of decision variables user76646 https://cs.stackexchange.com/users/76646 2018-05-13T00:38:19Z 2018-05-13T12:41:53Z <p>I am solving an optimization problem using SPEA2, my problem has three cases with decision variables 25, 50 and 100 in each case. I want to ask if there is some relationship between the number of variables and iterations of evolution process. I mean to say I run algorithm fewer times when decision variables are 25 than once they are 50. Thanks in advance.</p> https://cs.stackexchange.com/q/91417 1 Chromosome length in Genetic Algorithms Antonio https://cs.stackexchange.com/users/87963 2018-05-02T05:01:46Z 2018-05-02T05:01:46Z <p>In order to find the appropriate length of chromosomes in GA programming, the author of <a href="https://www.springer.com/us/book/9783540606765" rel="nofollow noreferrer">this book</a> states:</p> <blockquote> <p>Suppose six decimal places for the variables' values is desirable. It is clear that to achieve such precision each domain <em><code>Di = [ai,bi]</code></em> should be cut into <em><code>(bi - ai) * 10^6</code></em> equal size ranges. Let us denote by <em><code>mi</code></em> the smallest integer such that <em><code>(bi - ai) * 10^6 &lt;= 2^mi - 1</code></em>. Then, a representation having each variable <em><code>xi</code></em> coded as a binary string of length <em><code>mi</code></em> clearly satisfies the precision requirement. Additionally, the following formula interprets each such string:</p> <p><code>xi = ai + decimal(1001...001) * (bi - ai)/(2^mi - 1)</code> </p> <p>where <code>decimal(string)</code> represents the decimal value of that binary string.</p> </blockquote> <p>So here is my question: Why is the author using <code>(bi - ai)/(2^mi - 1)</code>? Why not <code>(bi - ai)/(2^mi)</code>? What is that <code>-1</code> for? </p> <p>I searched it and I thought it might have something to do with the Mersenne Prime numbers because of the formulation!! I also checked out the <a href="https://en.wikipedia.org/wiki/Schema_(genetic_algorithms)#Length" rel="nofollow noreferrer">Schema</a> as I thought it might be related to that, but these all seem completely unrelated!</p> https://cs.stackexchange.com/q/33735 1 The name for this genetic algorithm variant Przemek https://cs.stackexchange.com/users/24352 2014-12-02T16:07:38Z 2018-04-05T15:37:40Z <p>What is the name for this variant of genetic algorithm. I'm sure I have read about this in Wikipedia, but now I could not find it:</p> <p>There in no thing as sequential population. The phenotypes lives and dies just like people. The death comes after random period of time. During life phenotypes can have children. The better phenotype is (fitness function) the bigger is chance to have (more) children. The better phenotype is the better can be it's candidate form wife or husband. Yes, phenotypes have sex (man or woman).</p> https://cs.stackexchange.com/q/89886 0 How is Rank Selection better than Random selection and RWS? Haytam https://cs.stackexchange.com/users/85705 2018-03-27T23:39:54Z 2018-03-29T14:40:08Z <p>I'm having a rough time understanding the Rank Selection method for Genetic Algorithms. Here is what I think it does:</p> <ul> <li>Tour1's Fitness: 0.87 </li> <li>Tour2's Fitness: 1.22 </li> <li>Tour3's Fitness: 1.03</li> <li>Tour4's Fitness: 0.58</li> </ul> <p>We rank them using their fitness:</p> <ul> <li>4) Tour2 -- Highest rank (N)</li> <li>3) Tour3</li> <li>2) Tour1</li> <li>1) Tour4 -- Lowest rank (1)</li> </ul> <p>We generate a random number between 1 and 10 (sum of ranks), for example <code>X = 3</code>. We then loop and sum the ranks until its greater than X and we select the tour, in this example it will be <strong>Tour2</strong> since it's rank is 4 and <code>4 &gt; 3</code>.</p> <p>What I don't understand is how is this better than just randomly selecting a tour and why is it better than Roulette Wheel Selection? ALso please correct me if I'm missunderstanding the method.</p> https://cs.stackexchange.com/q/89834 2 Genetic algorithm - fit max circles inside box - what chromossomes? scottbear https://cs.stackexchange.com/users/86289 2018-03-26T19:59:11Z 2018-03-29T01:44:34Z <p>I am using a genetic algorithm to fit the max number of circles into a box. Right now my cromossomes are both coordinates of the each circle. I am not sure how to crossover and mutate the x and y coordenates in order not for the to converge but to keep a distance.</p> <p>Can someone please shed some light? Thank you</p> <p>This is where I am getting at: <a href="https://i.stack.imgur.com/rTccW.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/rTccW.jpg" alt="Result generation 1000"></a></p> <p>Now I am getting this: <a href="https://i.stack.imgur.com/elF5o.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/elF5o.jpg" alt="enter image description here"></a></p> <p>But there is the last ball always overlaps. I think my problem is with the crossover.</p> <p>So far and by gathering all the ideas here this is what I have reached: Given a fixed number of circles (easier to explain) this is what I am doing.</p> <ol> <li>Create a random set of circles for each individual in the population</li> </ol> <p><a href="https://i.stack.imgur.com/C1X8n.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/C1X8n.jpg" alt="Random circles"></a></p> <ol start="2"> <li><p>Calculate the fitness of every individual base on the overlaping area are and area outside the box.</p></li> <li><p>I then order the individuals by their fitness</p></li> <li><p>Do a cross over. For that I am using a cumulative sum to choose randomly but with priorities which individuals are likely to go through to the next generation based on the fitness. The fittest have a higher probability of being chosen.</p></li> <li><p>After choosing them indivudals I am aplying the crossover to I randomly choose the chromosse to which I do the single point cross over.</p></li> <li><p>Then repeat for n generations</p></li> </ol> <p>I am doing this but not getting to any convergion in terms of solution.</p> https://cs.stackexchange.com/q/89819 0 Genetic Algorithm - Fit max circles inside box scottbear https://cs.stackexchange.com/users/86289 2018-03-26T17:26:41Z 2018-03-26T18:06:21Z <p>I am using a genetic algorithm to find the best way to pack circles inside a box without each touching the others and filling as much space as possible. My doubt is if an individual from a generation must be a circle or all the circles. </p> <p>Can anyone help me on how would I go from here? Thank you</p> https://cs.stackexchange.com/q/89734 3 Are there are satisfying explanations for why genetic algorithms work? hawkeye https://cs.stackexchange.com/users/1709 2018-03-24T10:38:03Z 2018-03-24T11:42:28Z <p>The following commentator <a href="https://news.ycombinator.com/item?id=16650185" rel="nofollow noreferrer">writes</a>:</p> <blockquote> <p>Having studied this extensively back when they were called <a href="https://en.wikipedia.org/wiki/Genetic_algorithm" rel="nofollow noreferrer">Genetic Algorithms</a>, I would like to offer a few insights.</p> <p>One of the biggest reasons they fell out of favor for more "mathematical" approaches was that no one could really explain why exactly they worked. It makes sense on the surface that "survival of the fittest" and doing something akin to multiple stochastic gradient descents would work, but no one has really been able to produce a mathematical proof as to why.</p> <p>Since other folks are producing good examples of "explainable AI", I don't know how Genetic Algorithms/programming could be made 'explainable' as to why they achieved an optimal solution other than hand-waving to how evolution works in nature.</p> </blockquote> <p><a href="https://en.wikipedia.org/wiki/Stephen_Wolfram" rel="nofollow noreferrer">Steven Wolfram</a> has published the book <a href="https://en.wikipedia.org/wiki/A_New_Kind_of_Science" rel="nofollow noreferrer">A New Kind of Science</a>, in which he posits that mathematical proofs aren't relevant to this approach, and the algorithm is itself the science. Many <a href="https://math.stackexchange.com/a/1228669/109927">considered this</a> unsatisfactory. </p> <p>We know that Cellular Automaton <a href="https://en.wikipedia.org/wiki/Rule_110" rel="nofollow noreferrer">rule 110</a> is Turing complete. (And <a href="https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life">phenomenal things</a> have been done with Conway's Game of Life). </p> <p>My question is: <strong>Are there satisfying explanations for why genetic algorithms work?</strong></p> https://cs.stackexchange.com/q/89335 0 How to find the best parameters of a Genetic Algorithm applied to the TSP problem? Haytam https://cs.stackexchange.com/users/85705 2018-03-14T16:40:02Z 2018-03-14T16:40:02Z <p>I have an assignement where I need to use a Genetic Algorithm to solve the TSP (Traveling Salesman Problem). I alrerady implemented a solution in C# but the problem is we're asked to use some kind of method to do the Parameters Tunning (For example to pick the population size, mutation rate, etc..). For now, I only try random values and test..</p> <p>I tried looking for an example with Taguchi method but I don't seem to understand how would one implement it for a GA problem. </p> <p>Can anyone put me in the right direction?</p> https://cs.stackexchange.com/q/88344 1 Unknown length of chromosone in genetic algorithm Ferus https://cs.stackexchange.com/users/81338 2018-02-20T17:08:33Z 2018-02-20T17:08:33Z <p>I've read some about genetic algorithms and the general approach, but I haven't found anything about using it when the length of the solution is unknown. How would the generation of the initial population look like? Would mutation then include adding/removing alleless? Are there any general methods for this?</p> https://cs.stackexchange.com/q/88330 0 Evolutionary Algorithm and Correlation Kawamoto Takeshi https://cs.stackexchange.com/users/54006 2018-02-20T11:39:00Z 2018-02-20T11:39:00Z <p><em>Note: Not sure with the tags.</em></p> <p>I'm quite new to this area of Computer Science. I was used to just developing software and applications and applying certain algorithms when necessary. However, I am tasked right now with a very complex task. I apologize in advance, although being a Computer Science graduate, I've only been in the industry for at least 2 years. So, this specific requirement is really eating me up.</p> <p>Consider two time-series data sets:</p> <p><strong>Data Set 1</strong></p> <pre><code>Date Category Count 11/12/13 A 30 11/13/13 A 23 11/14/13 A 24 11/12/13 B 53 11/13/13 B 36 11/14/13 B 67 </code></pre> <p><strong>Data Set 2</strong></p> <pre><code>Date Category Count 11/12/13 C 44 11/13/13 C 12 11/14/13 C 62 11/12/13 D 26 11/13/13 D 73 11/14/13 D 62 </code></pre> <p>I was tasked to get which Category-pairs from D1 and D2 has the highest correlations. This was simple enough using Pearson or Kendall's</p> <p>For example (mock correlation values for example):</p> <pre><code>Category Pair Correlation A vs C 0.532222 A vs D 0.742221 B vs C 0.988888 B vs D 0.356666 </code></pre> <p>This was easy enough to do, so I just had to output that list in order from highest to lowest. But the thing is, my boss tells me that I should add an evolutionary algorithm to the program because the current algorithm I am doing to determine the correlation is of brute force where I pair each A to C, then D, and do the same with B. However, my boss tells me that if I use evolutionary algorithm, it will only take randomized pairs which will reduce performance time but still give a somewhat above average result.</p> <p>I am quite unsure with how to approach this. I've been reading on Evolutionary Algorithms for a while now but I can't seem to wrap my mind on how this time-series data set would fit into the algorithm.</p> <p>Am I supposed to apply the Evolutionary algorithm after the correlations have been computed? I can't seem to grasp why I need to do an evolutionary algorithm on such data sets? </p> <p>From my understanding, Evolutionary algorithm is like 'survival of the fittest', keeping the most optimized, and best values in the end.</p> <p>I am pretty sure my understanding of Evolutionary algorithms are still lacking, please do enlighten me. I am not a native English speaker but I'll try my best to understand. It would also be great if someone can point me to the right direction on how to approach the merging of these two concepts together.</p> https://cs.stackexchange.com/q/86549 1 How to construct the objective function for genetic algorithm optimization? K.n90 https://cs.stackexchange.com/users/82858 2018-01-10T22:17:36Z 2018-01-14T23:12:38Z <p>I am trying to optimize a coefficients of filter by minimizing sum-squared error. I want to use a <em>genetic algorithm</em> (GA) optimization wherein the coefficients of filter form the GA's chromosome (a vector).</p> <p>How can I construct the objective function, given that I want it to use least-squares minimization?</p> https://cs.stackexchange.com/q/86700 1 What is the point of selection step in a genetic algorithm? Eduard Valentin https://cs.stackexchange.com/users/71778 2018-01-13T21:35:58Z 2018-01-14T01:21:24Z <p>I'm reading about genetic algorithms, and I'm not sure I understand the point of selection step.Let's say we have a population of size $N$.How many chromosomes should we select using any selection method and what's the point if the population size is fixed ? </p> <p>From what I understood till now we select a number of chromosomes (I still don't know how many should we select) and let's say we use Proportionate Fitness selection method and we chose $k$ 'good' chromosomes, then only on those $k$ chromosomes we apply crossover and mutation and let the other unselected ones untouched to the next iteration ? I'm not sure I got it right.Someone can clarify this for me ? </p> <p>Thank you ! </p>