【《GA-SFLA耦合模型构建分析案例》4300字】

GA-SFLA耦合模型构建分析案例目录TOC\o"1-3"\h\u12699GA-SFLA耦合模型构建分析案例 1108221.1基本遗传算法及特点分析 13031.1.1GA计算流程 1109811.1.2GA的特点 238101.2基本混合蛙跳算法及特点分析 4149101.2.1SFLA计算流程 45431.2.2SFLA的特点 673701.3GA-SFLA耦合模型构建 71.1基本遗传算法及特点分析1.1.1GA计算流程GA是一种解决最优化问题的有效方法，其搜索机制基于自然选择和自然遗传。作为一种全局优化搜索算法，其整体思路如下：假设用一群“染色体”表示问题的求解，将它们放在由问题组成的“环境”中，根据达尔文的生物进化论，从初始种群中选择出最适应环境的“染色体”进行复制，通过类似生物进化基因的交叉和变异操作，产生更适应环境的新的一代“染色体”群，不断重复该过程，最后可得到最适合生存的个体，即现实中所求问题的最优解。其基本计算过程如下：1）遗传编码用一定长度的字符串来表达GA的编码，字符串类似于遗传学中的“染色体”，不同的字符代表染色体上的“基因”，用以存储和传递遗传信息，它是遗传算法运算的基本对象。常用的编码方法有二进制编码、整数编码等。2）产生初始种群在GA过程中，每一代由众多的个体（一定长度的字符串）组成，多个个体便形成一个种群，种群规模越大，搜索范围就越大，运算时间也就越长。通常情况下的种群规模以50~100为宜，第0代初始种群通过随机方法生成，是后面进化迭代的基础。3）确定适应度函数衡量种群中个体好坏以及其是否能遗传给下一代的标准是适应度值，也就是目标函数，以此来驱动整个进化过程。4）遗传算子（1）选择算子为体现生物进化过程中“适者生存、优胜劣汰”的自然选择法则，保证优良个体数量、提高新一代种群的品质，GA在每次迭代产生的种群中都选择一定数量的优良个体进入下一代种群进行遗传操作。在选择过程中，由目标函数确定的适应度值是该染色体被复制或被淘汰的决定性因素。常用的选择方法有轮盘赌选择、随机遍历抽样等。（2）交叉算子交叉是用以上选择方法从当前种群中选择两个父代个体，被选中的这两个父代个体执行部分编码的交叉组合，生成两个新的子代个体。交叉概率通常取值0.8以上，常用的交叉方法有：单点交叉、多点交叉和均匀交叉等。（3）变异算子变异是产生新个体产生的一种主要方法，直接改变染色体的编码，实现“质”的变化，使搜索过程跳出局部最优解得到全局最优解。对于二进制编码的定长字符串来说，变异就是随机按位取反，0变为1，1变为0。变异操作能够确保种群中基因的多样性，可在尽可能大的空间中进行遗传搜索迭代，避免迭代过程中丢失有用信息而陷入局部最优解。变异概率一般取值较小，在0.01~0.1之间为宜。5）设置迭代终止条件GA是一种反复迭代的搜索方法，通过对种群的多次迭代运算，使结果逐渐逼近最优解，因此为保证计算时间和效率，需要确定迭代终止条件。最常用的方法是预设迭代次数，通常设定为200左右，之后视情况调整；或是观察适应度值的变化情况，当种群整体适应度值或最优个体适应度值都变化很小时，便可终止迭代运算。6）染色体解码根据编码时设定的编码规则对最优个体解码，即可得到最终搜索结果。1.1.2GA的特点与其他常规优化算法相比，GA具有以下几方面特点:（1）GA要求推导公式和附加信息，确定适应度值的大小即可，对优化问题没有太高数学要求，对问题的依赖小。（2）GA的寻优规则不是确定性的，都是由其搜索概率决定的。（3）GA在解空间的搜索并非完全随机或盲目穷举，而是高效启发式的搜索。（4）GA可通过大规模并行计算提高计算速度和效率。虽然到目前有关GA进化机制的理论和应用还在持续探索中，但其在搜索复杂空间化问题上已取得较为显著的效果。因此，GA在求解土地空间资源优化配置问题上有着独特的优点：与常规方法相比，GA更能找到最逼近模型最优解的方案；GA的求解过程具有较强客观性，结果更令人满意和信服；应用GA进行智能化求解可大大减轻规划师们的负担。图3-1GA计算流程图1.2基本混合蛙跳算法及特点分析1.2.1SFLA计算流程SFLA假设在一块池塘中，有N只青蛙都在寻找食物最多的地方。整个青蛙群体可划分为多个不同的族群（memeplex），每个青蛙对食物最多地方有自己的决策信息，青蛙个体之间互相交流和影响，个体的决策信息进化导致族群也会进化，该过程称为“局部优化”。一定程度后，各个族群进行信息交换实现子群体间的混合运算，即“全局优化”。直到满足终止条件（全局最优解基本不变或全局优化次数达到上限）即可完成迭代。详细计算步骤如下：（1）初试化种群信息确定种群的数量，族群数量，每个族群中青蛙的数量，则。设定最大进化次数，为进化次数变量，为族群计数变量，、分别表示每个族群中性能最好、最差的青蛙，表示整个种群中性能最好的青蛙。每一轮的进化，都会改善最差青蛙的位置。（2）划分青蛙等级并分组将青蛙按适应度值降序排列，记录第一个最好青蛙（首个全局最优解）的位置。将个青蛙进行分组：个青蛙分配到个族群中，每个族群只青蛙。（3）局部优化（memetic进化）设，是族群计数器，用来与比较；设=0，代表组内进化次数，与族群最大进化比较。[Step1]：在第个族群中选取个可能成为最佳青蛙的青蛙构成“更小子群”（submemeplex），并确定“更小子群”中最佳青蛙和最差青蛙的位置、。。选取只青蛙的策略：给具有较高适应值的青蛙赋予更高的权重，具有较差适应值的青蛙赋较低权重。[Step2]改善子族群中最差青蛙的位置。，方法如下：青蛙移动的距离，forapositivestep，foranegativestep其中是的随机数，是被感染后青蛙允许移动的最大步长。然后计算新的位置,（表示当前位置，），计算新位置的适应度值，当前位置的适应度值为。图3-2计算示意图a.如果比好，则用新的替换。b.如果比差，则用全局最优替换局部最优。青蛙移动的距离，新的位置,计算新的适应值比旧的好，则用新的替换，否则执行。c.若上述方法仍不能生成更好的青蛙，就随机生成一个新解取代原来最差青蛙。[Step3]如果，则转到步骤3。如果，则转到步骤2，否则转到下一步全局搜索过程。（4）青蛙在memeplex之间跳跃在每个memeplex中执行了一定memetic局部优化之后，将优化后的族群重新组合在一起，再按适应度值降序排序，并更新种群中最好青蛙（第个全局最优解），判断是否满足迭代停止条件。是，停止。否则，返回Step2继续迭代。图3-3SFLA计算流程图1.2.2SFLA的特点SFLA具有演变过程简单、参数少、计算量小、计算速度快以及全局寻优能力强等可取之处，同时，GA具有并行化、较好的鲁棒性以及全局寻优能力较强等优点。但是，GA编程实现较为复杂、三种遗传算子实现需设置许多参数、容易“早熟”以及局部寻优能力较差等。因此，GA适用于快速求解、但精确度要求不高的情况。因此，本文通过采用GA和SFLA耦合构成的混合算法对土地利用优化配置进行实验研究与分析。1.3GA-SFLA耦合模型构建本研究整体流程以GA为主要框架，将SFLA的局部优化概念引入到选择算子中，耦合算法模型GA-SFLA原理如下：（1）将SFLA的局部优化引入到GA的选择过程中GA的核心内容是三个遗传算子，传统GA的选择方法如轮盘赌、随机抽样等方法是导致GA容易陷入局部最优的原因之一，因此为降低GA出现“早熟”或是陷入局部最优解的概率，本文在GA的选择过程引入SFLA的“先局部优化，后全局优化”的原理，将考虑全局适应度值后、适应度值高的个体选择出来，减少对局部较优解的破坏，在保持种群多样性的同时，大大地提高GA的收敛速度。该结果继续用于后续交叉、变异操作。图3-4GA-SFLA计算流程图引入SFLA中对种群分组的概念，将个体分组，每组内按照适应度值进行降序排列。组内进行SFLA的局部优化，替换掉最差个体，每个组局部优化后和其他组混合，在此根据适应度值进行降序排列，然后由适应度值按照轮盘赌的方法选择个体进入之后的操作。轮盘赌的基本思想是：每个个体被选中的概率与其适应度大小成正比。具体操作如下：=1\*GB3①计算出种群中每个个体的适应度，为种群大小=2\*GB3②计算出每个各个被遗传到下一代种群中的概率（3-1）=3\*GB3③计算出每个个体的累积概率（3-2）（称为染色体的积累概率）图3-5积累概率示意图=4\*GB3④在[0,1]区间内产生一个均匀分布的伪随机数=5\*GB3⑤若，则选择个体1，否则，选择个体，使得：成立=6\*GB3⑥重复=4\*GB3④、=5\*GB3⑤共M次（2）GA的交叉、变异采用自适应调节机制，而非设置固定概率传统GA在进化过程中使用固定的交叉和变异概率，即无论是优势个体、还是劣势个体都要进行相同概率的交叉、变异操作。这会导致两个问题：（1）设置相同的概率，对于进化的个体来说是不公平的。对于优良个体，应该减小交叉、变异概率使其得以保存；对于劣质个体，应该增大交叉、变异概率使其尽可能地发生改变。所以，一成不变的和会影响算法的计算效率。（2）相同的概率不能很好地满足种群进化过程中的需要。在种群进化初期，可快速筛选掉适应度差的个体，使得总体平均适应度值不断提高；在进化后期，种群需要较小的交叉、变异概率以保证种群在寻找完最优解后能够快速收敛。而固定算子对较优解的破坏更大，使收敛速度变慢。基于上述传统GA的交叉、变异过程存在的问题，，本文采用自适应进化机制(adaptiveevolutionarymechanism，AEM)ADDINZOTERO_ITEMCSL_CITATION{"citationID":"rVhTTJf6","properties":{"formattedCitation":"\\super[77]\\nosupersub{}","plainCitation":"[77]","noteIndex":0},"citationItems":[{"id":626,"uris":["/users/local/2sR1O8W8/items/5PBQC9BU"],"uri":["/users/local/2sR1O8W8/items/5PBQC9BU"],"itemData":{"id":626,"type":"article-journal","abstract":"Thevehicleroutingproblem(vehicleroutingproblem,VRPinremainderofthispaper)isacombinatorialoptimisationproblemandoperationalresearch.Itbelongstothecategoryoftransportationproblems,asthetravellingsalesmanproblem(travellingsalesmanproblem,TSP)andthechance-constrainedprogramming(CCP).Theseproblemsinthefieldoflogistics,oneormorevehiclesmustcovertransportationnetworktodelivergoodstocustomersorcovertheroadsnetwork.Solvingtheproblemistodetermineasetoftoursthatminimisethebesttargetsasthetotaldistancetravelled,thenumberofvehiclesused,thesumofthedelaysofcustomers,i.e.Thisarticledescribesanewalgorithmforsolvingtransportationproblemswithmodifiedboundaryconditionstominimisetheuncertaintyinthetravelparameters,whereagainisassociatedwitheachcustomerandwheretheobjectiveistomaximisethetotalgaincollectedandminimisetheroutingcosts.","container-title":"InternationalJournalofAdvancedIntelligenceParadigms","DOI":"10.1504/IJAIP.2016.077498","journalAbbreviation":"InternationalJournalofAdvancedIntelligenceParadigms","page":"318","source":"ResearchGate","title":"Adaptiveprobabilitiesofcrossoverandmutationingeneticalgorithmforsolvingstochasticvehicleroutingproblem","volume":"8","author":[{"family":"Ali","given":"Rekik"},{"family":"Mounir","given":"Gabsi"},{"family":"Moncef","given":"Temani"}],"issued":{"date-parts":[["2016",1,1]]}}}],"schema":"/citation-style-language/schema/raw/master/csl-citation.json"}[77]，在进化过程中根据适应度值自适应地调整和的值，当群体倾向于停留在局部最优时（即群体适应度集中，但多样性较差），和的值增大；当群体在解空间中散布时（即群体适应度分散，但多样性较高），和的值减小。在每代种群中，每个个体所对应的和应该是不同的，因为好的（适应度值高于群体平均适应值）的个体应该尽可能保存并进入下一代，对应较低的和；差的（适应度值低于群体平均适应值）个体应该尽可能进行交叉变异来产生新个体，对应较高的和。所以和的计算方法应该和每个个体的适应度值都有关ADDINZOTERO_ITEMCSL_CITATION{"citationID":"2O0tNkyw","properties":{"formattedCitation":"\\super[78,79]\\nosupersub{}","plainCitation":"[78,79]","noteIndex":0},"citationItems":[{"id":628,"uris":["/users/local/2sR1O8W8/items/AQZIFGRM"],"uri":["/users/local/2sR1O8W8/items/AQZIFGRM"],"itemData":{"id":628,"type":"article-journal","abstract":"Researchintoadjustingtheprobabilitiesofcrossoverandmutationpmingeneticalgorithms(GAs)isoneofthemostsignificantandpromisingareasinevolutionarycomputation.pxandpmgreatlydeterminewhetherthealgorithmwillfindanear-optimumsolutionorwhetheritwillfindasolutionefficiently.Insteadofusingfixedvaluesofpxandpm,thispaperpresentstheuseoffuzzylogictoadaptivelyadjustthevaluesofpxandpminGA.ByapplyingtheK-meansalgorithm,distributionofthepopulationinthesearchspaceisclusteredineachgeneration.Afuzzysystemisusedtoadjustthevaluesofpxandpm.Itisbasedonconsideringtherelativesizeoftheclustercontainingthebestchromosomeandtheonecontainingtheworstchromosome.Theproposedmethodhasbeenappliedtooptimizeabuckregulatorthatrequiressatisfyingseveralstaticanddynamicoperationalrequirements.Theoptimizedcircuitcomponentvalues,theregulator'sperformance,andtheconvergencerateinthetrainingarefavorablycomparedwiththeGAusingfixedvaluesofpxandpm.Theeffectivenessofthefuzzy-controlledcrossoverandmutationprobabilitiesisalsodemonstratedbyoptimizingeightmultidimensionalmathematicalfunctions","container-title":"IEEETransactionsonEvolutionaryComputation","DOI":"10.1109/TEVC.2006.880727","ISSN":"1941-0026","issue":"3","note":"event:IEEETransactionsonEvolutionaryComputation","page":"326-335","source":"IEEEXplore","title":"Clustering-BasedAdaptiveCrossoverandMutationProbabilitiesforGeneticAlgorithms","volume":"11","author":[{"family":"Zhang","given":"J."},{"family":"Chung","given":"H.S."},{"family":"Lo","given":"W."}],"issued":{"date-parts":[["2007",6]]}},"label":"page"},{"id":631,"uris":["/users/local/2sR1O8W8/items/2BEV67Y8"],"uri":["/users/local/2sR1O8W8/items/2BEV67Y8"],"itemData":{"id":631,"type":"article-journal","abstract":"介绍了遗传算法的起源以及基本概念。从模仿生物遗传进化的角度出发,在参考现有遗传算法的基础上设计一种可以随适应度变化而变化的遗传算法模型。现有的遗传算法往往计算度过于复杂,且容易过早收敛,不能得到精确解。通过该算法与标准遗传算法在选择的实验模型上比较,可以清楚地看到所改进的算法的优越性能。仿真表明,该模型不仅具有良好的实验效果,还有很高的进化效率,求得目标的成功性也高多了。","container-title":"计算机与现代化","ISSN":"1006-2475","issue":"12","language":"中文;","page":"12-14+18","source":"CNKI","title":"一种改进的遗传算法","URL":"/KCMS/detail/