遗传算法及其应用

遗传算法及其应用周新力（华东交通大学，江西南昌，330013）摘要：介绍了遗传算法的概念、步骤、特点和基本原理，分析了遗传算法的发展及研究情况，讨论了存在问题及改进措施。最后，从实际应用的角度对其重点的分析研究。关键字：遗传算法，优化，算子Abstract:Theconceptofgeneticalgorithmisintroduced,andthesteps,characteristicsandbasicprinciple,analyzesthedevelopmentandresearchofgeneticalgorithm,discussesthetheoryofgeneticalgorithmexistingproblemsandimprovementmeasures.Finally,fromthepracticalpointofviewonthekeyanalysisof.Keywords:Geneticalgorithm,optimization,operator0引言遗传算法是1975年由美国的Holland教授首次在他的专著《自然界和人工系统的适应性》中提出的，它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。由于广泛的实用价值，能解决任何种类实际问题，得到各领域的大力推广。2000年成立了专门的遗传算法国际会议，每2年举行一次，如今已举行了8次，对此研究的文献更是不胜枚举。因为遗传算法自身的特点，使得在搜索过程中优于启发式算法。1遗传算法概述1.1遗传算法的概念及特点遗传算法是一类借鉴生物界“物竞天择，适者生存”的进化规律演化而来的随机化搜索方法。该方法椒模拟生物进化过程和优胜劣汰遗传机制的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。由于其广泛地适用性，逐渐成为重要的智能算法之一。遗传算法具有以下特点：（1）从问题解的中集开始嫂索，而不是从单个解开始。这是遗传算法与不同于传统优化算法的关键点，由于遗传算法从串集开始搜索，覆盖面大，利于全局择优。（2）求解时使用特定问题的信息极少，容易形成通用算法程序。只需适应值和串编码等通用信息，便可几乎可处理任何问题。（3）很强的容错能力。遗传算法的初始串集本身就带有大量与最优解甚远的信息，通过选择、交叉、变异操作能迅速排除与最优解相差极大的串，这是一个强烈的滤波过程，并且是一个并行滤波机制。因而，遗传算法有较高的容错能力。（4）随机选择性。遗传算法是采用随机选择方式对最优解进行搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。1.2基本原理及步骤根据生物学上的进化论相关概念，遗传算法追求群体间出现比当前个体更具有能力的个体。因此，该方法的基本原理为：利用二进制组建遗传算法的初始种群，在每个串中，每个二进制就是个体染色体的基因，然后对该种群进行选择、交叉和变异操作，直到达到某个给定的值或个体适应度无变化后，结束上述操作。遗传算法的步骤：（1）初始化。选择一个串或个体的集合bi，i=1，2...n。一般情况下n取30-160。（2）选择。根据优胜劣汰遗传机制选取下一代个体，以适应度为选择原则。给出目标函数f，f(bi)称为个体bi的适应度，选中bi下一代个体的次数以公式nbjbifipnj)(}b{选中算出。（3）交叉。随机选取两个个体相同位置，按交叉概率p在相同位置交换。例如a=110010,b=010101;选择右边3位进行交换，结果为a=110101，b=010010。（4）变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率为mp,一般情况下mp取0.01-0.2。变异产生了新个体，增加了全局优化的特性。（5）全局最优收敛。通过选择、交叉和变异后，最优个体适应度达到给定值时，算法的迭代过程收敛、算法结束。该流程如图1所示.选择下一代交叉变异2遗传算法的发展遗传算法出现后，因为自身特性，被广泛运用。随着，应用领域的扩大和实际问题的复杂性逐渐出现一些不足，相关学者相继提出了一些方法:（1）保持物种多样性的遗传算法（2）多目标优化遗传算法（3）混合算法