文摘

遗传算法的性能依赖于遗传算子,在一般情况下,交叉算子的类型,特别是。人口多样性通常是作为衡量工作表现的过早收敛。本文提出了一种模糊遗传算法求解二进制编码的组合优化问题。提出了一种新的交叉算子和概率选择技术基于人口多样性使用模糊逻辑控制器。人口多样性的测量是基于基因型和表型属性。在这个模糊推理系统,交叉算子的选择及其概率控制的一组模糊规则来源于模糊逻辑控制器。广泛的计算对该算法进行了实验,结果与一些交叉运营商通常用于解决多维0/1背包问题发表在《文学。结果表明,该算法是有效的在寻找更好的解决方案。

1。介绍

过早收敛是一个常见的问题在寻找最优解的遗传算法(GA)和强烈相关损失的人口多样性。当人口多样性较低,GA会很快收敛。另一方面,如果太高,人口的多样性是非常耗时的GA收敛,这可能会造成计算资源的浪费。

遗传算法的性能依赖于一般遗传算子和交叉算子的类型,特别是。遗传算法在进化过程中,如果选中的染色体一致,一些交叉运营商未能创建后代,不同于他们的父母。有效的交叉遗传算法是通过建立之间的最优关系交叉和搜索问题本身。

本文提出了一种模糊遗传算法(FGA)求解二进制编码的组合优化问题,如多维0/1背包问题(MKP)。其目的是设计一个交叉算子和概率选择技术基于人口多样性使用模糊逻辑控制器(方法)。多样性的人口是衡量的基础上的基因型和表现型特征染色体。此外,基于汉明距离的新技术(HD)、健身价值(艘),和活跃的基因(AG)在性选择伴侣提出染色体。

近年来,MKP已经变成了试验metaheuristics的游乐场。作为适当的“困难”测试开发先进的技术在这一领域的问题。MKP一般声明任何二进制编码问题负的系数。它制定如下(Djannaty和Doostdar [1): 在哪里=数量的对象;=数量的背包;=消耗的资源为对象;=能力th背包;=利润与对象相关联;=决策变量与对象。

本文的其余部分组织如下。文献回顾下节中给出2。部分3阐述了人口的多样性。节4,提出了FGA详细描述。计算结果的FGA MKP基于基准问题实例从文学提出了部分放气5。最后,给出了一个简短的结论部分6。

2。文学

进化算法通常使用人口的多样性作为绩效指标等多种原因避免过早收敛,控制算法重新启动或停止人口多样性低于特定的阈值时,不同的帕累托最优解决方案的必要性评估人口在一个优化问题,并且需要快速适应人口动态问题(见Tomassini et al。2),莫里森和德容(3],和Wineberg Oppacher [4更多细节)。

人口多样性的一些文学侧重于遗传算子及其概率。Sywerda [5和德容和枪6)各种交叉算子相比,尤其是跨界点的数量。他们的研究结果表明,有时最终的输出会更好如果分频点的数量增加了。除了实证分析,投资比较实质性的努力,从理论的角度,变异和交叉以及各种之间交叉操作符(6]。然而,这些理论不够一般,以便预测何时应用或使用什么类型的交叉算子。例如,这些理论没有地址的大小研究人口即使它可能影响的相对有效性交叉算子(7]。同样,有足够的证据表明突变的相对有效性可能受人口的大小的影响。突变似乎更有利与种群规模小交叉,而交叉可能更有利的变异与人口众多的大小(8]。此外,变异和交叉的相对有效性受到其他因素的影响,适应度函数,表示,选择方案。

交叉概率的选择严重影响行为和遗传算法的性能。它控制的解决方案为每个问题的概率服从交叉,由用户选择。戈德堡和Sastry9广义的模式定理。他们认为,模式的选择压力对应的破坏,他们表明,当积木紧凑(它的基因在染色体相互靠近字符串),遗传算法适用于广泛的组合和选择压力。

自适应技术,改变应用一个算子的概率成正比的观测性能过程中染色体的运行提出了戴维斯(10]。费尔南德斯et al。11)认为是GA,适应人口的繁殖率的大小在调查之中。Annunziato和Pizzuti12)提出了一个技术设置的遗传参数在实现通过调整人口规模和运营商的利率环境约束的最大的人口规模。而另一方面,斯和Patnaik13)采用了一个混乱的方式的决心基于各种健身价值的人口。他们提出了一个方法,在交叉的遗传算法不需要参数。曹、吴(14)提出了一个系统的随机优化算法控制参数的天然气。在他们的研究中,遗传算法是模仿控制马尔可夫链的过渡依赖于控制的交叉和变异概率。香港et al。15]介绍了一个动态遗传算法,同时使用多个交叉和变异算子生成下一代。运营商的率是不同的评价结果各自的后代在下一代。

许多研究人员使用不同的参数作为输入变量的动态控制方法实现遗传算法的交叉和变异概率。歌等。16)的变更连续两代人之间的平均适应度值作为输入变量。Yun和创17]后引入一个比例因子归一化中使用的输入变量(16]。李等人。18利用信息的整整一代和特定的染色体作为输入变量。王等人。19)认为健身值连续两代人之间的差异,和刘et al。20.)使用的平均健身价值和最好的健身价值在每一代染色体作为输入变量。

高木涉(李和21)被认为是三个模糊系统的输入:,是最好的变化适应性自上次输入变量控制行动和平均,最好和最差的健身价值,分别。介绍了对应于这些输入3输出当前人口规模,交叉概率和变异概率。他们测试了该技术在倒立摆控制的任务(22]。然而,这种技术有两个主要缺陷:(我)只使用表型特征作为输入变量,(2)使用元级遗传算法找到动态参数化的遗传算法优化模糊系统是计算昂贵。

我和李23)提出了自适应交叉、变异和选择使用模糊系统气体。然而,目前尚不清楚如何模糊系统是建立和参数的遗传算法用于选择规则和隶属度函数。

方法的主要问题是如何获得模糊规则推理系统是基于。提出了几种方法自动识别规则库。一个家庭的细菌类型进化算法已成功申请解决这个任务。我们的目标是创建更精确的模糊规则基地尽快从输入输出数据集。全面回顾这些bacterial-type进化算法给出了(24]。

3所示。人口的多样性

本研究中采用的方法试图定义一个度量种群多样性的基础上,基因型和表型特征。问题可能会提出为什么表现型和基因型特征一起使用。将使用一个简单的例子来回答这个问题。让是一个线性函数的最大值需要定义如下: 解决(3.1使用GA),让我们说5染色体长度为15的初始种群。在表1人口,目的是评估基于基因型多样性属性。激活,染色体之间的HDs最高的健身价值和其他染色体计算。注意,高清可以定义如下。

定义3.1(汉明距离)。让和内两条染色体长度的人口之间的汉明距离(HD)和是 在哪里

见表1高清是最多2,染色体的长度是15。这意味着人口的遗传多样性较低。然而,考虑到染色体的阵线,范围是相对较高的。因此,染色体的基因型属性本身并不足够解释人口的多样性。

在表2,不同的初始种群是用来评估基于表型的人口多样性的财产。为了达到这个目标,染色体的阵线。见表2,差异的范围的染色体阵线很低,因此人口的多样性似乎低虽然染色体之间的HD高。因此,染色体的表型属性本身并不足够证明人口的多样性。

根据这一点,基因型和表型属性都被认为是本文的测量的人口多样性。在表型措施的情况下,提出的方法斯和Patnaik [13和朱和刘25使用用细微的修改: 在哪里=人口规模,=数量的人群中独特的健身价值,在一代最大的健身价值t和在一代=平均健身价值。

在基因型的措施的情况下,一个方程类似Jassadapakorn提出的技术的一部分,Chongstitvatana [26使用: 在哪里=高清染色体之间的最高和最低的阵线,和l=染色体的长度。

在这个技术,高清计算在每一代只有两条染色体:染色体最大的健身价值和最低的健身价值。应该强调,在的方法26),计算高清第一选择染色体和候选人之间的染色体,在那里。因此,我们提出的方法需要更少的时间比(26]。

,属于区间。随着和接近零,染色体的阵线几乎完全相同,这表明收敛发生而如果这些是接近1,显示了一个高水平的人口多样性。类似地,如果是接近于零,那么遗传多样性较低,人口有可能收敛很快。如果是附近,显示了一个高水平的遗传多样性。

当我们说的人口多样性低、中等或高的多样性,我们可以看到,语言成为一个模糊变量空间的外延是不精确的。在这个意义上,模糊理论变得容易理解,因为它可以像一个高级语言,而不是数学语言。来描述,模糊集的名字如低,介质,或高是用来创建一个成员函数。通过确定的隶属程度输入模糊集的隶属函数,可以看到隶属度函数的作用发挥在解码语言术语计算机可以使用的值。在大多数情况下,隶属度函数是由专家知识系统的设计进行了分析。在这篇文章中,关于,,定义了三个隶属度函数。语言相关的标签的集合和很低,中,高,那些有关吗低和高。这些标签的语义含义如图1。

4所示。模糊遗传算法

在本节中,我们集中精力的讨论提出了解决FGA二进制编码的组合优化问题具体MKP节中定义1。在本节的其余部分,我们解释了拟议的框架FGA见图2更多细节。

4.1。基因表达和人口

MKP,解决方案可以简单地由一个字符串编码0和1的年代,在“1”编码,一个项目被选中,“0”的意思。染色体的长度对应的条目的数量MKP。

一个好的初始种群使它容易GA收敛于良好的解决方案,而贫困人口普查的初步可以延长GA收敛。有不同的方法生成初始种群遗传算法。最常见的方法是通过随机生成。在本文中,我们使用随机生成方法提出的楚和比斯利27人群中实现更好的多样性。给出了初始种群的伪代码的算法1。注意,在实现人口规模保持不变。

创建新的后代后通过交叉和变异操作,可能会有一些孩子不可行的解决方案。有几种方法来处理不可行解的遗传算法如下所述: 只利用一个编码方法产生可行的解决方案, 应用一个修复机制将任何不可行的解决方案转换成一个可行的解决方案, 单独的健身之间的可行和不可行解决方案的评估,或者 应用罚函数惩罚任何不扭曲市场的情况下不可行解的健身健身景观。

在本文中,我们使用修复算子引入了楚和比斯利27),将一个不可行的解决方案转换成算法提出了一个可行的解决方案2。

4.2。性选择

在标准遗传算法,染色体无性繁殖,即任何两个染色体可能交叉的父母。性别分工和性选择激励模型的性别遗传算法交叉发生只有染色体之间的异性。由于遗传算法模仿自然进化,那么性别遗传算法是关键因素之一。

灵感来自于nongenetic在一些爬行动物性别决定系统普遍性是由温度决定的蛋孵化,人口划分,男性和女性会选择以另一种方式。男性和女性染色体的布局在每一代都是不同的。换句话说,当一代的数目是偶数,染色体和分别是男性和女性,反之亦然时生成的数量是奇数。例如,假设一个人口规模是5,雄性和雌性的布局从这个人口如表所示3。

在提出性选择,选择一位女性染色体通过锦标赛选择大小从女性群体。选择的女性染色体和female_chro表示。另一方面,男性染色体的选择(male_chro)交叉是基于从female_chro高清,阵线、AG)的男性染色体。注意,AG)可以定义如下。

定义4.1(活跃的基因)。活跃的基因用非零的基因在染色体的数量吗。例如,让,然后。
起初,从男性组男性染色体随机选择。然后,male_chro被选中时,偏好的基础上的 最大的高清男性染色体和female_chro之间, 最高的男性染色体阵线(如果多于一个男性染色体有最大的高清), 最高的男性染色体AG(如果多于一个男性染色体拥有最高的阵线是发现),或 随机选择。

的计算实验提出了性选择比其他选择机制从文献中可以找到Varnamkhasti和李28]。MKPs计算结果比较表明,该性选择机制在提供高质量的解决方案在合理的执行时间。

4.3。模糊交叉算子和概率

在本节中,我们提出一个交叉算子和概率选择技术基于人口多样性的使用方法。选择最合适的交叉算子、交叉和人口结构的多样性必须考虑。在本文中,一些常用的交叉操作的二进制编码是默认的交叉算子。这些运营商和他们的缩写词表4。值得一提的是,如果不根据给定的应用交叉概率,那么这两个孩子只是父母的副本。

当人口的遗传多样性高2 pc运营商执行相对其他交叉算子相比,特别是在计算时间。遗传多样性的人口中当一些位点的染色体是相同的。在这种情况下,2 pc操作符不是一个合适的选择,但是,KPC和加州大学运营商将会更合适。运营商都能保持遗传多样性的人口同时提高染色体的适应度值。另一方面,人口的遗传多样性较低当一些染色体是相同的。2 pc、KPC和加州大学运营商未能产生后代,不同于他们的父母。在这种情况下,SC和IC运营商将会更合适。基于上述解释的相对交叉算子和遗传多样性,为交叉能力三个层次(CA)称为低,中,高介绍和展示在表5。

正如前面所讨论的,遗传多样性不足以证明整个人口的多样性。因此,我们提出一个模糊系统需要三个输入变量,产生两个输出变量:,输入变量而CA和吗输出变量。语言标签的集合与输出变量包括相关的描述低,中,高。对于每一个语言学术语,有三角模糊集定义其语义,如图3。

语言规则描述控制系统由两部分构成:一个先行词块(之间的如果和然后)和一个顺向块(然后)。通过这种类型的评估,更少的规则可以被评估,从而简化了处理逻辑,甚至改善模糊逻辑系统的性能。每个规则有可能产生一个单一的规则为每个输出变量。摘要输入组合逻辑上使用和/或操作符生成输出和响应值的所有预期的输入: 在哪里。

因此,提出模糊系统有三个输入变量将有18所示为每个输出变量(CA和规则)。这个集体提出了模糊规则库表6。所有规则的模糊输出最终聚合到一个模糊集,获得清晰的决定从这个模糊集,我们使用重心对去模糊化方法:

4.4。精英主义替代过滤

后,应用模糊交叉和标准二进制变异算子,精英主义替代技术用作替代策略。后代必须与他们的父母为了让竞争过渡到新的人口。换句话说,钳工染色体将为下一代的生存,他们从未失去,除非找到更好的解决方案。精英主义的替代技术,两个父母和后代的数量被认为是一起为一个单一的人口。那么这个人口nonincreasing顺序排序相关的健身价值和染色体从这个结合上半年人口被选为新的人口为下一代的染色体。

是什么意思,在这种背景下,说两个染色体的基因座基因是相等的。存在相同的染色体是过早收敛的关键问题之一。当一个大型染色体的人口比例是相同的,人口的多样性将丢失和过早收敛。为了克服这个问题,过滤技术是用于添加新的人口的多样性。在这种技术,保持相同的染色体,而其他人则删除,取而代之的是新的可行染色体是随机生成的。随着过滤过程涉及“识别”的过程,“再生”和“重新评估”的新染色体,这需要一定的计算时间,这是明智的每个调用这个过程一代(是一个参数,例如,100)或当至少有10%的人口都是相同的。

5。计算结果

摘要基准数据集测试包括270 MKPs提出了(27]。这个数据集是在文献中广泛使用的测试MKP算法。这些问题包括变量和约束。为每个类别的变量,三个紧张比率被认为是。这一系列的问题包含27个不同的习题,各有10个随机生成的实例,因此总共有270个问题。

在这些习题,从离散均匀发电机吗和右边系数,设置使用在哪里紧张的比率。目标函数系数是相关的和生成,在那里是实数的连续统一的发电机吗。

这些方法的性能是衡量基准之间的偏差(PD)比例问题从ORLibrary [29日和我们的结果,即: 在哪里是基准测试结果吗由该算法所获得的计算结果。

为了审查的性能和能力提出FGA标准遗传算法(sga)相比,表中提到的交叉算子4用于计算实验。之间的差异提出了FGA SGA是关于交叉算子的使用及其概率。换句话说,SGA将雇用一个交叉算子与固定的概率,在实现。因此,将会有五个sga相比FGA之一的实验。每个算法实现与人口规模100人。性选择中所描述的部分4所示。2,替换策略部分中解释4所示。4和标准二进制变异概率(是染色体的长度)被用作默认的遗传算子。

所有算法都是用c++编写的,运行在一个奔腾IV, 2.0 GHz CPU和2.0 GB的内存。对于每个问题实例,30进行运行。为了有一个公平的比较算法在这个实验中,我们使用一个CPU时间20秒/运行。结果列在表中7。基准列表示平均10个问题实例的计算结果从每个问题集的MKPs编译(29日]。对于每个算法,PD计算平均超过10项报告问题实例30分,300分。为每个类别的,最后一行给出了平均PD的所有值。表的最后一行7给出了总体平均PD所有类别。

我们第一次观察到FGA的表现明显比sga。这表明FGA sga相比能够产生更好的质量解决方案在一个固定的CPU时间。有明确的证据可以证明表7平均,FGA是最好的SGA和SC算法,集成电路,用户体验,KPC,最后2 pc的SGA。算法找到的问题最具挑战性的。与其他的事情(例如,和)不变的情况下,当我们增加的价值,然后PD将会增加。注意,所有的算法,减少代执行的期限内随着背包或约束的数量变得更大。

6。结论

遗传算法通常使用人口的多样性作为衡量工作表现等诸多原因避免过早收敛。本文提出了人口多样性的测量技术基于表型和基因型的属性。本研究的主要贡献是交叉算子和概率选择技术基于人口多样性使用模糊逻辑控制器。提出了模糊遗传算法的性能比其他标准遗传算法求解多维0/1背包问题表明,该算法是有效的找到更好的和类似的解决方案。

未来的研究工作将调查提出的模糊遗传算法扩展到包括模糊变异算子和概率选择技术其他二进制编码的组合优化问题。此外,我们可以考虑扩展研究整数编码的模糊遗传算法。