grasshopper-galapagos遗传算法【精品毕业设计】(完整版)

Evolutionary Principles applied to

Problem Solving

遗传算法

There is nothing particularly new about Evolutionary Solvers or Genetic Algorithms. The first references to this field of computation stem from the early 60's when Lawrence J. Fogel published the landmark paper "On the Organization of Intellect" which sparked the first endeavours into evolutionary computing. The early 70's witnessed further forays with seminal work produced by -among others- Ingo Rechenberg and John Henry Holland. Evolutionary Computation didn't gain popularity beyond the programmer world until Richard Dawkins' book "The Blind Watchmaker" in 1986, which came with a small program that generated a seemingly endless stream of body-plans called "Bio-morphs" based on human selection. Since the 80's the advent of the personal computer has made it possible for individuals without government funding to apply evolutionary principles to personal projects and they have since made it into the common parlance.

其实在遗传算法和基因算法里并什么特别新的理论出现，该领域的第一篇文献出现在六十年代由Lawrence J. Fogel 出版的具有里程碑意义的论文“智能组织”，这篇论文使人们开始致力于研究遗传算法。七十年代又由ngo Rechenberg and John Henry Holland的工作进一步带动了基因算法的发展，遗传算法直到1986年才因为Richard Dawkins的“The Blind Watchmake”而让人广

为人知，里面有个小的例子，基于人类的选择仍然会产生无尽的被称为“生态形变”的动作计划。80年代由于个人电脑的出现使得每个人都可以将进化算法用于个人项目而不用政府提供资金支持，从此，进化算法开始像日常话题一样进入公众视野。

The term "Evolutionary Computing" may very well be widely known at this point in time, but they are still very much a programmers tool. 'By programmers for programmers' if you will. The applications out there that apply evolutionary logic are either aimed at solving specific problems, or they are generic libraries that allow other programmers to

piggyback along. It is my hope that Galapagos will provide a generic platform for the application of Evolutionary Algorithms to be used on a wide variety of problems by non-programmers.

虽然现在进化算法在现在已经广为人知，但他大部分还作为编程工具使用，只是程序员和程序员之间交流，遗传算法即使应用也是处理一些特别的问题，大部分时间还是呆在通用库里等着程序员来用它，我希望galapagos可以提供一个遗传算法的广泛平台来让那些非编程人员来处理一些问题。

Pros and Cons

赞成和反对

Before we dive into the subject matter too deeply though I feel it is important to highlight some of the (dis)advantages of this particular type of solver, just so you know what to expect. Since we are not living in the best of all possible worlds there is often no such thing as the perfect solution. Every approach has drawbacks and limitations. In the case of Evolutionary Algorithms these are luckily well known and easily understood drawbacks, even though they are not trivial. Indeed, they may well be prohibitive for many a particular problem.

在我们深入探讨这个问题之前，我认为有必要向大家介绍这类特殊算法处理方式的优缺点，这样可能更利于你了解你到底想通过这个获得什么。事实上我们生活在一个不完美的世界，没有什么事情会有一个完美地解决方案，每个解决方案都会有他的缺陷和限制。而在遗传算法领域可喜的是我们明确地知道他的一些缺陷，而且这些缺陷也不小，而且确实在一些具体问题的处理上明确禁止用遗传算法来解决。

Firstly; Evolutionary Algorithms are slow. Dead slow. It is not unheard of that a single process may run for days or even weeks. Especially complicated set-ups that require a long time in order to solve a single iteration will quickly run out of hand. A light/shadow or acoustic computation for example may easily take a minute per iteration. If we assume we'll need at least 50 generations of 50 individuals each (which is almost certainly an underestimate unless the problem has a very obvious solution.) we're already looking at a two-day runtime.

首先，遗传算法在运行起来的时候很慢，奇慢，非常慢，慢的要死。一个小程序运行几天甚至几个星期一点也不见怪，尤其是需要长时间简单迭代的复杂数据结构，运行起来会马上超出你的掌控，就算简单的光影分析或者是声学分析每次迭代就要几分钟，假设我们设置50代，每代50个个体（这都是按照最少最理想的状态来设定的），那这个程序需要两天才能做完。

Secondly, Evolutionary Algorithms do not guarantee a solution. Unless a predefined

'good-enough' value is specified, the process will tend to run on indefinitely, never reaching The Answer, or, having reached it, not recognizing it for what it is.

其次，遗传算法并不能百分之百的保证求出正确的解，除非一个预先你已经想好的差不多的解已经确定下来，遗传算法会尽量的朝着你想要的那个解努力，但是他永远不会找到“真理”，当然，也可能找到了只不过他是电脑，根本意识不到那个是最优解，即“真理”。

All is not bleak and dismal however, Evolutionary Algorithms have strong benefits as well, some of them rather unique amongst the plethora of computational methods. They are remarkably flexible for example, able to tackle a wide variety of problems. There are classes of problems which are by definition beyond the reach of even the best solver implementation and other classes that are very difficult to solve, but these are typically rare in the province of the human meso-world. By and large the problems we encounter on a daily basis fall into the 'evolutionary solvable' category.

当然，遗传算法也并不是上面我说的那么单调无力，一直被吐槽。进化算法在一些方面也有着强大的性能体现，在茫茫多的计算算法里他确实一枝独秀，进化算法有很强的灵活性，能同时处理各种各样的问题，有些问题最好的解算器也解不出来，而且很多的我们日常遇到的问题都可以放到进化算法的范畴内进行解决。

Evolutionary Algorithms are also quite forgiving. They will happily chew on problems that have been under- or over-constrained or otherwise poorly formulated. Furthermore, because the run-time process is progressive, intermediate answers can be harvested at practically any time. Unlike many dedicated algorithms, Evolutionary Solvers spew forth a never ending stream of answers, where newer answers are generally of a higher quality than older answers. So even a pre-maturely aborted run will yield something which could be called a result. It might not be a very good result, but it will be a result of sorts.

进化算法的容忍性也很好，他很有能力去处理一些你低估或者高估或者很傻X的操作，进一步讲，因为它运行的时候是动态的，所以你在任何时候都可以收获一大堆的解而不像其他解算法（解完了才能得到答案），进化算法射出来一大堆永远没有尽头的解，而且这一代的解总体上来说会比上一代的质量更高，所以，尽管一些早产的结果产生我们也可以姑且把他认为是结果，虽然他不是最优秀的结果，但是他确是得到最优结果必不可少的一部分。

Finally, Evolutionary Solvers allow -in principle- for a high degree of interaction with the user. This too is a fairly unique feature, especially given the broad range of possible applications. The run-time process is highly transparent and browsable, and there exists a lot of opportunity for a dialogue between algorithm and human. The solver can be coached across barriers with the aid of human intelligence, or it can be goaded into exploring sub-optimal branches and superficially dead-ends.

最后讲一点，进化算法和用户有很强的交互性，这是非常特别独特的属性，特别是当你给了他一大堆可能的条件是。当他在运行起来的时候，求解过程非常透明也便于浏览，因此存在很多机会创建人机交互的对话窗口，引导解算跨过障碍，或者探索一些并不是很理想的答案，甚至一条死胡同。

The Process

运行特点

In this section I shall briefly outline the process of an Evolutionary Solver run. It is a highly simplified version of the remainder of the blog post, and I'll skip over many interesting and even important details. I'll show the process as a series of image frames, where each frame shows the state of the 'population' at a given moment in time. Before I can start however, I need to explain what the image below means.

在这段里我将简单的介绍一下进化算法是如何运行的，这些内容都是以前一些博客简化了的，所以忽略了一些有趣甚至重要的细节。下面我会用一系列的图片来展示他是如何运行的，每一张图都记录了在特定时刻的“代”的关系，在开始之前，我先解释一下下图是啥意思。

What you see here is the Fitness Landscape of a particular model. The model contains two variables, meaning two values which are allowed to change. In Evolutionary Computing we refer to variables as genes. As we change Gene A, the state of the model changes and it either becomes better or worse (depending on what we're looking for). So as Gene A changes, the fitness of the entire model goes up or down. But for every value of A, we can also vary Gene B, resulting in better or worse combinations of A and B. Every combination of A and B results in a particular fitness, and this fitness is expressed as the height of the Fitness Landscape. It is the job of the solver to find the highest peak in this landscape.

你可以把上面这张图当成一个特别的景观模型（类似于山脉），这个模型包涵了两个变量，他们可以同时变化。在进化算法中我们习惯把变量称为基因。当我们改变基因A的时候结果会变好或者变坏（取决于我们希望他变好还是变坏）来匹配适合模型的状态。所以，当基因A改变时，整个模型都在变化。同理，在基因A发生变化时，基因B也可以同时参与变化，这时候出来的结果就是A和B同时起的作用。每一个A和B所产生出来的结果都被反映在这个模型的Z轴高度上，因为我们的任务就是找

出来这个山峰的最高点。

Of course a lot of problems are defined by not just two but many genes, in which case we can no longer speak of a 'landscape' in the strict sense. A model with 12 genes would be a 12-dimensional fitness volume deformed in 13 dimensions instead of a

two-dimensional fitness plane deformed in 3 dimensions. As this is impossible to visualize I shall only use one and two-dimensional models, but note that when we speak of a "landscape", it might mean something terribly more complex than the above image shows.

诚然，大量的问题并非简单的通过两个基因就能确定，而是需要很多基因，所以严格意义上来讲的话也就不能用景观（山脉）这个概念来解释，你想想看，一个用12个变量确定的将会是一个12维体扭曲在13维空间里，而不再是2维平面扭曲在三维空间里。所以我用一个2维的模型是不可能展示出来12维物体的，不过我提到这个只是想说有时候我们研究的要比上面这个2维世界的图复杂得多。

As the solver starts it has no idea about the actual shape of the fitness landscape. Indeed, if we knew the shape we wouldn't need to bother with all this messy evolutionary stuff in the first place. So the initial step of the solver is to populate the landscape (or "model-space") with a random collection of individuals (or "genomes"). A genome is nothing more than a specific value for each and every gene. In the above case, a genome could for example be {A=0.2 B=0.5}. The solver will then evaluate the fitness for each and every one of these random genomes, giving us the following distribution:

当这个进化算法开始的时候，其实电脑是不知道这个山脉景观的，如果电脑会像我们一样一眼看出来这个山脉的高低一开始就不用这么麻烦的去弄一大堆的数据。所以，在一开始，电脑就要用一大堆随机的点（基因组）来给他塑形。基因组就是一组数据，没别的，在这个例子里，一个基因组就相当于A=0.2 B=0.5的一个坐标。电脑计算过每一个随机的基因组，并且适应化之后，我们就可以看到下图这样的分布。