下载  >  课程资源  >  专业指导  > A Genetic Algorithm Tutorial

A Genetic Algorithm Tutorial 评分

遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。
If soine paraIneter can only take onl all exact finite set of values then the coding issue becomes more difficult. For example, what if there are exactly 1200 discrete values which can be assigned to some variable Xi. We need at least ll bits to cover this range, b this codes for a total of 2048 discrete values. The 848 unnecessary bit patterns may result n no evaluation, a default worst possible evaluation, or some parameter settings may be represented twice so that all binary strings result in a legal set of parameter values. Solving such coding problcms is usually considcrcd to be part of thc dcsign of thc cvaluation function Aside from the coding issue, the evaluation function is usually given as part of the problem description. On the other hand, developing an evaluation function can sometimes involve developing a simulation. In other cases, the evaluation may be performance based and may represent only an approximate or partial evaluation. For example, consider a contro application where the system can be in any one of an exponentially large number of possible states. Assume a genetic algorithm is used to optimize some form of control strategy. In such cases, the state space must be sampled in a limited fashion and the resulting evaluation of control strategies is approximate and noisy(c f, Fitzpatrick and Grefenstette, 1988) The evaluation function must, also be relatively fast. This is typically true for any opti- mization method, but it may particularly pose an issue for genetic algorithms. Since a genetic algorithm works with a population of potential solutions, it incurs the cost of cvaluating this population. Furthermore, the population is replaced (all or in part )on a generational basis The members of the population reproduce, and their offspring must then be evaluated. If it takes 1 hour to do al evaluation, then it takes over 1 year to do 10,000 evaluatiOns. This ld be approximately 50 generations for a population of only 200 strings 1.2 How hard is hard? Assuming the interaction between parameters is nonlinear. the size of the search space is related to the number of bits used in the problem encoding. For a bit string encoding of length L, the size of the search space is 2 and forms a hypercube. The genetic algorithm samples the corners of this L-dimensional hy percube Generally, Inost test functions are at least 30 bits in length and mlost researchers would probably agree that larger test functions are needed. Anything much smaller represents a space which can be enumerated. (Considering for a moment that the national debt of the United States in 1993 is approximately 22 dollars, 2 does not sound quite so large. )Of course, the expression 2 grows exponen tia lly with respect to L. Consider a problem with an encoding of 400 bits. How big is the associated search space? A classic introductory textbook on Artificial Intelligence gives one characterization of a space of this size. Winston (1992: 102) points out that 240 is a good approximation of the effective size of the search space of possible board configurations in chess.(This assumes the effective branching factor at each possible inove to be 16 and that a gale is Illade up of 100 Inoves; 1600=(24)00=2400) Winston states that this is "a ridiculously large number. In fact, if all the atoms in the universe had been computing chess moves at picosecond rates since the big bang (if any) the analysis would be just getting started The point is tha at as long as the numb ber of "good solutions"to a problem are sparse with respect to thc sizc of thc scarch spacc, then random scarch or scarch by cnumcration of a largc 3 search space is niot a practical forin of probleIn solving. On the other hand, any search other than random search imposes some bias in terms of how it looks for better solutions and where it looks in the search space. Genetic algorithms indeed introduce a particular bias in terms of what new points in the space will be sampled. Nevertheless, a genetic algorithm belongs to the class of met hods known as wea k methods in the artificial Intelligence community because it makes relatively few assumptions about the problem that is being solved Of course, there are many optimiz ation methods that have been developed in mathe- matics and operations research. What role do genetic algorithms play as an optimization tool? Genetic algorithms are often described as a global search method that does not use gradient information. Thus, nondifferentiable functions as well as functions with multiple local optima represent classes of problems to which genetic algorithms might be applied Genetic algorithms, as a weak method, are robust but very general. If there exists a good specialized optimization method for a specilic problem, then genetic algorithm may not be the best optimization tool for that application. On the other hand, some researchers work with hy brid algorithms that combine existing methods with genetic algorithms 2 The Canonical Genetic Algorithm The first step in the implementation of any genetic algorithm is to generate an initial pop ulation. In the canonical genetic algorithm each member of this population will be a binar string of length L which corresponds to the problem encoding. Each string is sometimes referred to as a genotype(Holland, 1975)or, alternatively, a "chromosome"(Schaffer 1987). In most cases the initial population is generated randomly. After creating an initial population, each string is then evaluated and assigned a fitness value The notion of evaluation and fitnEss are sometimes used interchangeably. However is useful to distinguish between the evaluation function and the fitness function used by a genetic algorithm. In this tutorial, the evaluation function, or objective function, provides a measure of performance with respect to a particular set of parameters. The fitness function transforms that measure of performance into an allocation of reproductive opportunities The evaluation of a string representing a set, of parameters is independent, of the eva luation of any other string. The fitness of that string, however, is always defined with respect to othcr members of the current population In the canonical genetic algorithm, fitness is defined by: fi/f where fi is the evaluation associated with string i and f is the average evaluation of all the strings in the population Fitness can also be assigned based on a strings rank in the population Baker, 1985; Whitley 1989)or by sampling methods, such as tournament selection( Goldberg. 1990) It is helpful to view the execution of the genetic algorithm as a two stage process. It starts with the current population. Selection is applied to the current population to create an intermediate population. Then recombination and mutation are applied to the intermediate population to create the nect population. The process of going from the current population to the next population constitutes one generation in the execution of a genetic algorithm Goldberg(1989 )refers to this basic implementation as a Simple Genetic Algorithm (SGA) Figure 1: One generation is broken down into a selection phase and recombination phase This figure shows strings being assigned into adjacent slots during selection. In fact, they can be assigned slots randomly in order to shuffle the intermediate population. Mutation(not shown) can be applied after crossover. We will first consider the construction of the intermediate population from the currer i.e., duplicated) and placed in the intermediate generation is proportion to their fitness, 2 g population. In the first generation the current population is also the initial population. After calculating fi/f for all the strings in the current population, selection is carried out. In the canonical genetic a. hm the probability that st rings in the current population are copie There are a number of ways to do selection. We might view the population as mapping onto a roulette wheel, where each individual is represented by a space that proportionally corresponds to its fitness. By repeatedly spinning the roulette wheel, individuals are chosen using "stochastic sampling with replacementto fill the intermediate population A selection process that will more closely match the expected fitness values is "remainder stochastic sampling. For each string i where fi/f is greater than 1.0, the integer portion of this number indicates how many copies of that string are directly placed in the intermediate population. All strings(including thosc with fi/f less than 1.0)thon placc additional copics in the intermediate population with a probability corresponding to the fractional portion of f ilf. For example, a string with fi/f= 1.36 places 1 copy in the intermediate population an then receives a 0.36 chance of placing a second copy. A string with a fitness of fi /f=0.54 has a0. 54 chance of placing one string in the intermediate population Remainder stochastic sampling"is Inost efficiently iMplemented using a Inethod knOwL as Stochastic Universal sampling. A ssUme that the population is laid out in random order as in a pie graph, where each individual is assigned space on the pie graph in proportion to fitness. Next an outer roulette wheel is placed around the pie with equally space pointers. A single spin of the roulette wheel will now simultaneously pick all n members of the intermediate population. The resulting selection is also unbiased(Baker, 1987) After selection has been carried out the construction of the intermediate population is complete and recombination can occur. This can be viewed as creating the next population from the intermediate population. Crossover is applied to randomly paired strings with a probability denoted Pc. (The population should already be sufficien tl y shufFled by the strings to form two new strings that are inserted into the next population recombine random selection process. Pick a pair of strings. With probability po the Consider the following binary string: 1101001100101101. The string would represent a possible solution to some parameter optimization problem. New sample points in the space are generated by recombining two parent strings. Consider the string 1101001100101101 and anot her binary string, yxyyxyxxyyyxyxxy, in which the values 0 and 1 are denoted by x and y. Using a single randomly chosen recombination point, 1-point crossover occurs as follows 11010\/01100101101 yxyyⅹ yxxyyyxyxxy Swapping the fragments between the two parents produces the following offspring 11010yxxyyyxyxxy yxyyxO1100101101 After recombination, we can apply a mutation operator. For each bit in the population mutate with some low probability pm. Typically the mutation rate is applied with less than 1% probability. In somle cases, Mutation is interpreted as randomly generating a new bit in which case, only 50% of the time will the"mutation"actually change the bit value. Ii other cases, mutation is interpreted to mean actually dipping the bit. The difference is no more than an implementation detail as long as the user/reader is aware of the difference and understands that the irst form of mutation produces a change in bit values only hall as often as the second, and that one version of mutation is just a scaled version of the other After the process of selection, recombination and mutation is complete, the next popu lation can be evaluated. The process of evaluation, selection, recombination and mutatio. orms one generation in the execution of a genetic algorithm 2. 1 Why does it work? Search Spaces as Hypercubes The question that most people who are new to the field of genetic algorithms ask at this point is why such a process should do anything useful. Why should one believe that this is going to result in an effective form of search or optimization? The answer which is most widely given to explain the computational behavior of genetic algorithms came out of John Hollands work. In his classic 1975 book, Adaptation in Nat ural and Artificial Systems, Holland develops several arguments designed to explain how a genetic plan"or "genetic algorithIll"call result in complex and robust search by implicitly sampling hyperplane partitions of a search space Perhaps the best way to understand how a genetic algorithm can sample hyperplane partitions is to consider a simple 3-dimension al space(see Figure 2). Assume we have a problem encoded with just 3 bits; this can be represented as a simple cube with the string 000 at the origin. Thc corners in this cubc arc numbered by bit strings and all adjacent corners are labelled by bit strings that differ by exactly 1-bit. An example is given in the top of Figure 2. The front plane of the cube contains all the points that begin with 0 If "* is used as a"dont care"or wild card match symbol, then this plane can also be represented by the special string 0*. Strings that contain *are referred to as schemata; each schema corresponds to a hyperplane in the search space. The"order"of a hy perplane refers to the number of actual bit values that appear in its schema. Thus, 1 ** is order-1 hie1米米1×*米来米*∩米米 would be of order- 3 The bottom of Figure 2 illustrates a 4 dimensional space represented by a cube"hanging inside another cube. The points can be labeled as follows. Label the points in the inner cube and outer cube exactly as they are labeled in the top 3-dimensional space. Next, prefix each inner cube labeling with a 1 bit and each outer cube labeling with a 0 bit. This creates an assignment to the points in hyperspace that givcs the propcr adjaccncy in the spacc bctwccn strings that are l bit different. The inner cube now corresponds to the hyperplane 1-**x while the outer cube corresponds to 0 *. It is also rather easy to see that 0* corresponds to the subset of points that corres ponds to the fronts of both cubes. The order-2 hy perplane 10%X corresponds to the front of the inner cube a bit string matches a particular schemata if that bit string can be constructed from the schemata by replacing the "symbol with the appropriate bit value. In general, all bit strings that match a particular schemata are contained in the hyperplane partition rep resented by that particular schemata. Every binary encoding is a "chromosome"which corresponds to a corner in the hypercube and is a member of l_ different hy perplanesy where l is the length of th ne binary encodin ng.The string of all y symbois corresponds to the space itself and is not counted as a partition of the space(Holland 1975: 72)). This can be shown by taking a bit string and looking at all the possible ways that any subset of bits can be replaced by "x symbols. In other words, there are L positions in the bit string and each position can be either the bit value contained in the string or the " symbo It is also relatively easy to see that 3l-l hyperplane partitions can be defined over the entire search space. For each of the L positions in the bit string we can have either the value 1 or o which results in 3 combinations. Establishing that each string is a member of 2-1 hyperplane partitions doesnt provide vcry much information if cach point in thc scarch spacc is cxamincd in isolation. This is why the notion of a population based search is critical to genetic algorithms. A population of sample points provides information about numerous hyperplanes furthermore, low order hyperplanes should be sampled by numerous points in the population.(This issue is reexam- ined in more detail in subsequent sections of this paper. ) A key part of a genetic algorithms intrinsic or implicit parallelism is derived from the fact that many hyperplanes are sampled when a population of strings is evaluated(Holland 1975); in fact, it can be argued that far more hyperplanes are sampled than the number of strings contained in the population. many Figure 2 A 3-dimensional cube and a f-dimEnsional hypercube. The corners of the inner cube and outer cube in the bottom i-Decample are numbered in the same way as in the upper 3-D cube, e ccept a 1 is added as u pr'efir to the labels of inner cube und a0 is added as a prefix to the labels of the outer cube. Only select points are labeled in the d-D hypercube different hy perplalles are evaluated in an implicitly parallel fashion each time a single string is evaluated(Holland 1975: 74); but it is the cumulative effects of evaluating a population of points that provides statistical information about any particular subset of hyperplanes Implicit paralle lism implies that many hy perplane competitions are simult aneously solved in parallel. The theory suggests that through the process of reproduction and recombination the schemata of competing hyperplanes incrcasc or dccrcasc thcir reprcscntation in thc pop ulation according to the relative fitness of the strings that lie in those hyperplane partitions Because genetic algorithms operate on populations of strings, one can track the proportional representation of a single schema representing a particular hyperplane in a population and indicate whether that hyperplane will increase or decrease its representation in the popula tion over time when fitness based selection is combined with crossover to produce offsprin from existing strings in the population 3 Two Views of Hyperplane sampling Another way of looking at hyperplane partitions is presented in Figure 3. A function over a single variable is plotted as a one-dimensional space, with function maximization as a goal The hyperplane 0*k*x. *k spans the first half of the space and 1** spans the second half of the space. Since the strings in the 0***K... ** partition are on average better than those in the 1*xxX. partition, we would like the search to be proportionally biased toward this partition. In the second graph the portion of the space corresponding to *1**.*is shaded, which also highlights the intersection of 0*x*..* and 1**... * namely,0*1 Finally, in the third graph, 0*10*..is highlighted One of the points of Figure 3 is that the sampling of hyperplane partitions is not reall errected by local optima. At the same time, increasing the sampling rate of partitions that are above average compared to other competing partitions does llot guarantee convergence to a global optimum. The global optimum could be a relatively isolated peak, for example Nevertheless, good solutions that are globally competitive should be found It is also a useful exercise to look at an example of a simple genetic algorithm in action In Table 1, the first 3 bits of each string are given explicitly while the remainder of the bit positions arc unspccificd. Thc goal is to look at only thosc hyperplanes dcfincd ovcr the first 3 bit positions in order to see what actually happens during the selection phase when strings are duplicated according to fitness. The theory behind genetic algorithms suggests that the new distribution of points in each hyperplane should change according to the average fitness of the strings in the population that are contained in the corresponding hyperplane partition Thus, even though a genetic algorithm never explicitly evaluates any particular hy perplane partition, it should change the distribution of string copies as if it had Holland initially used the term intrinsic parallelism in his 1975 monograph, then decided to switch to implicit parallelism to avoid confusion with terminology in parallel computing. Unfortunately, the term implicit parallelism in the parallel computing community refers to parallelism which is extracted from code written in functional languages that have no explicit parallel constructs. Implicit parallelism does not refer to the potential for running genetic algorithms on parallel hardware, although genetic algorithms are generally lewes as highly parallelizable algorithIns ×× Figure 3: A function and various partitions of hyperspace. Fitness is scaled to ao to l range in this diagram

...展开详情
所需积分/C币:5 上传时间:2019-01-01 资源大小:387KB
举报 举报 收藏 收藏
分享 分享
智能二代(Genetic Algorithm)饲料配方软件

智能二代(Genetic Algorithm)饲料配方软件,氨基酸比例最佳模型计算猪鸡配方

立即下载
genetic algorithm implementation in python

用python來實現遺傳算法的一篇文章 genetic algorithm implementation in python

立即下载
genetic algorithm

genetic algorithm of MATLAB。Beginners to use, simple, part of the function can be achieved.

立即下载
饲料配方大师2015免费版

饲料配方大师2015免费版,完全免费。免注册

立即下载
Comparative Analysis of Genetic Algorithm Implementations

遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。

立即下载
A simple genetic algorithm

Stephen J. Hartley * This Java code was derived from the C code in the Appendix of "Genetic * Algorithms + Data Structures = Evolution Programs," by Zbigniew * Michalewicz, Second Extended Edition, New York: Springer-Verlag (1994). * Other ideas and code were drawn from AGAC by Bill Spears (12

立即下载
ModbusTCP/RTU网关设计

基于UIP协议栈,实现MODBUS联网,可参考本文档资料,有MODBUS协议介绍

立即下载
html+css+js制作的一个动态的新年贺卡

该代码是http://blog.csdn.net/qq_29656961/article/details/78155792博客里面的代码,代码里面有要用到的图片资源和音乐资源。

立即下载
iCopy解码软件v1.0.1.7.exe

解ic,id,hid卡密码破解ic,id,hid卡密码破解ic,id,hid破解ic,id,hid卡破解ic,id,hid卡密码密码卡密码破解ic,id,hid卡...

立即下载
分布式服务框架原理与实践(高清完整版)

第1章应用架构演进1 1.1传统垂直应用架构2 1.1.1垂直应用架构介绍2 1.1.2垂直应用架构面临的挑战4 1.2RPC架构6 1.2.1RPC框架原理6 1.2.2最简单的RPC框架实现8 1.2.3业界主流RPC框架14 1.2.4RPC框架面临的挑战17 1.3SOA服务化架构18 1.3.1面向服务设计的原则18 1.3.2服务治理19 1.4微服务架构21 1.4.1什么是微服务21 1.4.2微服务架构对比SOA22 1.5总结23 第2章分布式服务框架入门25 2.1分布式服务框架诞生背景26 2.1.1应用从集中式走向分布式.26?

立即下载
Camtasia 9安装及破解方法绝对有效

附件中注册方法亲测有效,加以整理与大家共享。 由于附件大于60m传不上去,另附Camtasia 9百度云下载地址。免费自取 链接:http://pan.baidu.com/s/1kVABnhH 密码:xees

立即下载
电磁场与电磁波第四版谢处方 PDF

电磁场与电磁波第四版谢处方 (清晰版),做天线设计的可以作为参考。

立即下载
压缩包爆破解密工具(7z、rar、zip)

压缩包内包含三个工具,分别可以用来爆破解密7z压缩包、rar压缩包和zip压缩包。

立即下载
source insight 4.0.0087 注册机序列号Patched(2017/10/17)

最新的sourceinsight4.0.0087和谐license及和谐文件。真正的4087版本,使用附件中的license文件,替换sourceinsight4.exe

立即下载
Java项目经验汇总(简历项目素材)

Java项目经验汇总(简历项目素材)

立即下载
ssm整合solr

spring整合 solr部署到Tomcat,spring整合 solr部署到Tomcat

立即下载