混合粒子群算法研究

混合粒子群算法研究1.1引言粒子群优化算法是通过模拟自然界中鸟群觅食行为抽象出来的群智能优化算法，现已被广泛应用到流水车间调度、路径最优化选取、神经网络治疗等多个领域。本章结合实际应用过程中的问题及粒子群算法特点，提出一种混合粒子群算法。1.2标准粒子群算法标准粒子群算法是在1995年由R.Eberhart和J.Kennedy两位研究学者提出来的，是一种群智能优化算法，通过自然界中鸟群觅食行为抽象出来的优化算法，它把实际问题遍历区域看成搜索空间，将鸟群中的个体看作单独粒子，搜索空间中每个粒子均有自己的初始位置和初始速度，当鸟群中发现有觅食食物时，搜索空间中的每一个粒子受自身和其他粒子影响，重新赋予位置及速度，以此类推，通过多次迭代搜索，直至找到目标位置。粒子群算法是一种并行算法，其原理简单易懂，参数少，目前已经用于最优路径选取、流水车间调度、神经网络治疗等领域。1.2.1粒子群算法的数学模型由N个粒子组成的一个群体，在D维的搜素空间中，xi表示第i个粒子在搜索空间中的位置，所有的粒子的搜索空间中以一定速度在搜索空间中运行。在每一次迭代更新后，粒子以自身速度与其他粒子对其本身的影响更新自己运行的速度与新位置。通过评价函数评定每一个粒子迭代后的好快，保留粒子个体最优解和全局最优解。其速度及位置更新公式如下：1.2.2粒子群算法基本操作步骤标准粒子群算法处理优化问题操作步骤如下：步骤一：初始化粒子。在D维搜索空间中随机初始化种群粒子N，并赋予每个粒子初始速度v。步骤二：适应度函数评价机制。对搜索空间中每个粒子进行适应度评价机制，判断粒子当前最优解位置。步骤三：迭代更新。通过迭代更新和适应度函数判断，更新每个粒子位置及迭代速度，更新当前最优位置及全局最优位置。步骤四：找出最优解。依据寻优精度，判断是否结束寻优过程。如达到寻优精度或迭代次数，符合条件，找到最优解，结束寻优算法；如没有达到寻优精度或迭代次数，返回步骤二，继续验证适应度函数，进行迭代寻优更新。适应度函数一般为目标函数，根据求解问题的不同而不同，适应度值越高，代表所得解越好，越接近目标位置，一般使用f（x）代表适应度函数。1.3混合粒子群算法PSO算法尽管具有原理简单、参数少、容易实现等诸多优点，但是由于每次迭代更新需要通过自身认知和社会其他粒子影响的共同作用下进行的，进而导致使粒子容易陷入局部最优区域而找不到全局最优解。本文对粒子群算法进行如下改进：添加局部搜索算法，提高算法搜索精度，动态调节种群多样性，从根源消除算法容易陷入局部极值的缺点。1.3.1局部搜索算法鉴于PSO算法搜索精度低，容易陷入局部极值等缺点，因此提高局部搜索精度、增强种群多样性成为提高优化算法得整体思路，在优化算法中，惯性权重值得引入，使得算法在搜索初期对搜索空间中所有粒子进行全局大范围搜索，体现了智能算法得全局性，随着更新迭代的进行，逐步搜索到某一局部区域，算法只会在局部内进行搜索，而无法跳出当前局部搜索空间，这一现象被称为陷入局部极值。在粒子迭代过程中，搜索空间中设定有多个局部极值，在PSO算法中，粒子更新会同时收到自身惯性及周围粒子影响进行搜索，进而随机性陷入某一个局部极值无法跳出。本文引入模拟退火机制，实现局部搜索的精确搜索，引入变异策略，增强种群多样性，跳出局部最优概率。1.3.2退火机制模拟退火机制可理解为三个阶段：（1）加温。假定固态物体内部粒子原先处于不平衡状态，当把固态物体加热，内部粒子会因为温度的升高而偏离相对稳定的状态，直到液化固态物体，内部粒子打破原来状态，达到相对均匀。（2）平衡。当外界不再加热，物体由于自身温度高于外界温度，将与外界进行温度置换，物体内部粒子能量减少，当物体与外界温度一致时，此时物体内部能量最少，系统达到平衡。（3）冷却。当进一步将物体冷却，系统内能量进一步减少，物体内部粒子相对稳定，系统达到稳定。模拟退火算法具有很好的局部搜索能力，主要因为它可以接受比当前解更差的解，在模拟退火算法初期，随着温度的升高，算法不接受或小概率接受最优解，逐渐到算法后期，随着温度降低，最优解接受概率较高，可以容纳比当前最优解较差的解，有利于算法跳出局部极值。模拟退火算法思想如下：产生可行邻域解。模拟退火算法是邻域搜索算法，利用Metropolis接受机制，有几率产生比当前全局最优粒子差的邻域解，使算法有概率跳出局部极值。设优化目标函数为f（x），当前迭代次数时全局最优解为fx1，产生邻域解为fx2，两者差值设定df=fx2-fx1，则Metropolis准则接受邻域值得概率p为：P=由此公式可以看出，当df<0时，一定会产生新的邻域解，即还有达到局部最优状态；当df>=0时，算法以***概率接受邻域解，即当前全局最优解好了邻域解时，产生概率p是温度T得增函数，当T减少时概率p也减少，即体现算法后期邻域搜索能力较强特性。初温及降温设定。初温设定一般较大，能够使得所有转移状态都被接受，但也不宜过大，否则算法搜索时间过长，本文取t=1000作为初始温度。其降温公式为：****，t为迭代次数，从公式可以看出，随着t得增加，温度降低。终止温度。当模拟退火算法内、外循环在每一次迭代没有产生新的更新状态或已经达到设定的温度下限，即看成完成寻优任务，终止循环。1.3.3编码与解码优化问题中粒子编码就是所求优化问题得所有解得表达方式。编码得选取直接影响粒子群算法得优化性能，需符合调度方案，可以映射调度问题得解空间，能够适应粒子群算法中位置、速度得迭代更新。在车间调度问题中，粒子编码可以选取得种类很多，可从工件、工序、机器等进行编码，比较编码复杂性和时间复杂度来说，本文选取工序编码方式进行。解码是相对于编码而言的，简单概括编码是将具体问题抽象化，建立数学模型，便于求解，解码是将所得数据还原具体问题当中，从而进行评估、选择。现有3个工件需要加工，每个工件需要加工3道工序，采用工序编码，下图给出一组可行解。1313212231.1可行解编码如图所示，图中1、2、3代表工业生产中工件编码，在可行解编码中出现的位置代表加工的有效顺序，以第一件工件为例，出现的位置分别为1号、3号、6号位，即代表工件1分别在对应的位置进行工序1、工序2、工序3得加工工作，以此类推，图1只是给出一个可行编码解，代表工件加工顺序优先级。1.3.3交叉与变异交叉与变异操作是遗传算法得重要手段，是通过生物进化而得来的准则。交叉操作是指子代中继承父代有利基因，淘汰不利基因；变异是将原有基因序列某一片段进行修改，进而增强子代基因，通过交叉变异操作可以提高子代基因种类。由粒子群公式可以看出，粒子迭代后速度更新由自身与群体其他粒子均有影响，正是因为由本身历史最优粒子和全局最优粒子得影响下，保持向全局最优粒子靠拢，从而实现子代更新迭代。由此可知，交叉操作是父代在参考群体搜索经验当中进行的，子代在继承父代有利基因外，还将继承群体经验中交叉变异后的有利基因，这样增加了跳出局部极值得概率。粒子群算法不能动态实现种群更新，本文引入交叉变异操作提高粒子群算法种群动态更新。（1）交叉操作选定需要进行交叉操作的两个父代粒子x1、x2，将x1粒子随机选中和保留粒子的基因位，并记录选中基因个数，在x2粒子随机选中与x1粒子选中基因数相同的粒子，并保留其所在基因位，复制到新一代y粒子当中，将x1粒子中未选中基因按照顺序重新插入到y粒子中，所得新的基因序列即为交叉操作所得粒子。交叉操作示意图：（2）变异操作在粒子群算法中引入变异操作，也是提高种群多样性的有效途径，引导算法指向更高的适应度函数进化，在邻域搜索算法中，引入变异操作，使粒子产生邻域解，增强种群多样性，有易于跳出当前迭代极值，实现全局搜索。在基于工序编码的车间调度问题当中，变异操作是随机选择父代中一个粒子基因片段的不同基因位进行互换，需要强调的是，一个基因片段可以互相调换多组基因位，如果调换位置基因位相同，则父代基因与变异后子代基因相同，则实质上没有进行变异。以3*3车间调度问题为背景对其变异过程如图所示：1.4静态车间调度求解混合粒子群算法根据车间调度问题提出，为了验证混合粒子群算法在车间调度问题中的应用，首先采用静态车间调度问题，采用matlab测试软件进行模拟仿真实验，验证结果。1.4.1建立数学模型确定车间调度问题的输入输出是建立数学模型的关键，我们以工件个体及加工时间为输入对象，输出则以甘特图表示最佳调度流程，经过限制条件、智能算法优化、最终达到求解最优值。车间调度问题数学模型图如下：1.4.2仿真实验本文选取较为常见的FT06实例进行仿真测试实验，FT06实例描述为一批待加工6个工件，6台加工机器，每个工件需要加工6道工序，求解如何加工工件顺序使得加工时间最少，效率最高。具体工件及加工时间如下表：FT06实例问题目前达到的最好解为55。利用混合粒子群算法求解的FT06问题得出甘特图如图3.2，图中以工件加工总消耗时间为横坐标，以工件编号为纵坐标，以矩形框表示工件加工顺序。为了进一步验证混合粒子群算法在实例当中收敛性、鲁棒性，同时选取了DPSO、GA算法进行模拟对比实验，在FT06实例问题上三种算法分别求解10次，每种算法迭代200次，选取每一次迭代全局最优解平均值做出如图**所示，图中以每种算法迭代次数为横坐标，以每次迭代中全局最优值平均值为纵坐标。从图中可以看出，混合粒子群算法在收敛速度和收敛效果上都比DPSO、GA算