改进的果蝇优化算法在多目标搜索中的应用

张斌艳，罗万成，杨志刚

(重庆文理学院，重庆402160)

0 引言

果蝇优化算法是一种十分先进的仿生学算法，于2011年被首次提出．研究者通过观察果蝇生物的觅食方法，推导得出全局优化技术，从而完成局部搜索的任务需求，在科学以及工程领域都有着较为广泛的应用．但是，由于算法理论的诞生较晚，一些理论尚未完全成熟，因此更多表现为局部最优解和早熟收敛等弊端．为了能够在多目标搜索中发挥作用，需要对其进行优化．在当前的研究当中，果蝇优化算法主要集中在单一目标的优化之上，而对离散环境多目标的优化存在一定不足，笔者为了能够准确地实现多目标检索，需要进行算法的改进．

1 果蝇优化算法的改进方法

1.1果蝇优化算法的使用

果蝇优化算法最早于2011年被首次提出，研究人员观察了果蝇等生物的觅食以及生活习惯后发现，果蝇在空中飞翔的过程中，能够通过嗅觉以及视觉来判断空气当中存有的气味，并根据气味的大小和散播规律来判断食物源的具体方向，从而完成食物位置或同伴位置的确定，形成觅食流程的最优化．研究人员通过对这一现象进行分析总结，构成FOA算法．算法当中，step1代表果蝇群的位置，作为整个算法当中的初始算法参数，需要通过sisepop来表示果蝇的群体规模，而用maxgen表示算法的最大迭代次数，因此在坐标当中可以通过x、y来表示具体的初始化位置，如x(axis)和y(axis)[1]．step2则表示果蝇群体在觅食过程中的方向以及位置的选择，研究人员通过搜索距离的取值方法确定randomvalue的范围，如公式(1)所示：

Xi=X_axis+randomvalue

Yi=Y_axis+randomvalue

(1)

通过公式(1)，研究人员可以获得进行觅食的果蝇群体的位置范围区间．而step3则表示果蝇在判断空气气息浓度时的判断值si，并用disti表示判断值si的距离．如公式(2)和公式(3)所示．

(2)

si=1/disti

(3)

在判断的过程中，果蝇会根据浓度的判断值进行精确的位置判断，而在运用算法时则需要利用fitnessfunction适应度函数进行判定值的代入计算，从而获得浓度个体的判定值smelli，如公式(4)所示．

smelli=function(si)

(4)

而为了能够准确模拟浓度判断最佳的果蝇，要利用最佳的个体位置通过视觉引导群体向个体不断靠拢，最终完成群体最优浓度的更新，此时需要算法完成对公式(5)、公式(6)以及公式(7)的联立，从而实现最优解．

semllbest=bestsmell

(5)

X_axis=X(bestindex)

(6)

Y_axis=Y(bestindex)

(7)

在完成上述步骤之后，需要进行迭代，寻找最优解．通过不断重复执行的方式达到迭代的次数要求，以提高精度和准确度．

1.2 果蝇优化算法改进

传统的果蝇优化算法，虽然能够在一定程度上模拟果蝇觅食对空气气息浓度的最优判断，但是在实际的迭代过程中，由于最优个体学习策略的不断深化会加快收敛速度，导致种族多样性分析的丢失，最终造成局部最优，无法体现出最优解的要求．因此对于传统的果蝇优化算法来说，其所具有的单目标问题解决的特征使其无法直接应用在多目标的环境当中．在进行多目标搜索优化研究时，研究人员如果盲目地通过果蝇优化算法进行多目标的离散环境判断，很可能造成最劣解的随机选择，因此在进行改进时，需要进一步控制环境的连续性，通过个体的产生和变化来进行位置维度变化的记录，从而在前期迭代当中寻求多数解，最终通过半径计算的方法进行区域内部的密集检索，如公式(8)所示：

radius(搜索半径)=radiusmax·elg(rediusmin/radiusmax)·(g/maxgen)

(8)

在公式(8)当中，radius代表搜索半径，可通过极值max和min分别表示最大搜索半径和最小搜索半径，而字母g则表示在算法当中的实时迭代次数．maxgen表示迭代的极值，即最大迭代次数．在函数分析中，radius(1,10)表示radiusmax不会超过10，不会小于1，因此搜索半径的曲线变化呈单调递减的趋势，且随着迭代次数的不断增加，搜索半径会快速减少．而为了能够准确解决多目标离散环境中对问题最优的要求，需要根据迭代和搜索半径的变化规律进行优化算法改进．笔者在进行优化时采用新个体产生的方法，使其在种群位置当中表现为局部优化外的最优解计算方式，如公式(9)所示.

IND(i)=mod(X+radius·randval，upper)+1

(9)

在公式(9)当中，radius表示动态搜索半径，在具体计算时可由公式(8)进行计算和推导，而X表示果蝇种群的具体位置，可由公式(1)进行推导计算，upper表示算法的上界，randval表示随机范围的取值，在本文算法当中，表示{-1,0,1}．

2 多目标优化的算法要求

多目标的最优化问题实际上是数学当中的优化问题，一般通过数学定义的方式完成公式化的表达，如公式(10)所示．

minf(x)

St.gi(x)≤a1，i=1,2，…，m

(10)

公式(10)当中，x作为向量，表示最优化函数当中所拥有的自变量，而函数f(x)则作为Rii→R当中的目标求解，因此用来表示R变化的函数gi实际上应当属于一个约束不等式，从而为常数a提供约束条件和临界值，进而使x可以作为问题的最优解．在数学模型当中，当向量x的目标函数值为最小值时，表示任何满足gi函数且小于等于常数a的向量都应当具备f(x)≤f(s)，因此在求得最大值时，就可以通过相反数的方式将f(x)表示为-f(x)，进而根据目标函数和约束条件方程获得极值的优化[2]．

3 多目标搜索中果蝇优化算法的应用

3.1 混合步长嗅觉MFOA参数

在车间的设计当中，主要问题集中在车间设备所具有的功率、效率以及搬运量、搬运距离等因素，因此为了能够更好地完成车间设备的布置，降低调度成本，需要设定多因素的NP-hard问题，并基于果蝇优化算法形成多目标果蝇优化算法MFOA．

3.2 MFOA编码

在实例当中，车间的调度和设备布置问题实际上是多目标的离散优化问题，因此为了满足调度最优，在进行车间设备的布局以及加工顺序的设定时，需要在工序和设备的配置方面通过编码的方式对所需要进行选用的设备进行标签化处理，不同的设备拥有不同的编号，从而使其能够更好地表现在算法当中．

3.3 果蝇优化算法种群初始化

在完成针对车间内部的设备排序编码后，需要依照果蝇优化算法MFOA进行种群的初始化．通过初始化完成population个体的设置和产生．在设置中，算法需要兼顾population所拥有的质量以及多样性，因此在population当中40%的个体需要通过贪心算法产生，而剩下的部分则主要依靠随机方式生成．一般来说，如果运用贪心算法产生个体，则需要采用两种贪心策略：一种是通过选择加工时间短的机床，优先完成最早的工件加工，从而避免与另一个零件冲突：另一种则是优先对碳排放较低的工件进行加工，从而控制加工成本，实现调度优化．

3.4 混合步长嗅觉的应用

由于本文所针对的车间优化问题空间较大，因此离散问题也较多，为了能够准确地实现果蝇优化算法的最优解多目标优化，应当采用混合步长进行搜索，尽可能避免单一步长的领域搜索．具体来说，在算法完成第一次迭代之后，需要依照离散问题的生成而展开多种步长的邻域搜索，并将嗅觉搜索作为基础的操作原理，同时将基本操作标记为mutation operation．在算法当中，基本操作mutation operation是基于工序所完成的变异操作，同时在变异操作的基础之上通过设备布局完成操作．

3.5 全局协作

果蝇在进行觅食和空气气息浓度分析时，会采用种群间的学习方法获取信息，并不断进行自我位置的更新，而在算法当中设备编码由于受到工序的约束[3]，因此与果蝇在获取信息的过程所表现的特征相同，一般需要通过F1和F2不同个体的基因随机选择来确定位置信息，在完成信息步骤后，通过差分信息的方式，将信息依照大小完成排列，最终得到变化位置调整后的Fr编码信息，完成优化．

4 结语

在目前的科学技术领域和工程设计领域中，果蝇优化算法有着丰富的应用前景．而在多目标搜索的离散环境当中，由于所选目标数量较多，单一的果蝇优化算法无法完成计算，因此需要通过改进的MFOA算法来完成目标优化．