基于局部搜索的改进SPEA2算法

由于追求收敛速度与防止陷入局部最优,标准的改进强度Pareto算法(SPEA2)过于注重全局搜索能力,从而导致局部搜索能力不足.为了增强SPEA2算法的局部搜索性能,进而提高算法收敛速度,提出了一种基于局部搜索的改进SPEA2算法.该算法单独设置一个新外部存档集以保存局部搜索后的非支配集,并且改进了交叉算子,加入了部分个体更新策略.将该改进算法与SPEA2算法进行了收敛性能比较实验.仿真实验结果表明,相比于标准算法,改进SPEA2算法不仅可以保证收敛到多目标优化问题的Pareto最优边界,而且在收敛能力上也得到了较好的改善.     

教与同伴学习粒子群算法求解多目标柔性作业车间调度问题

针对多目标柔性作业车间调度问题,提出了带Pareto非支配解集的教与同伴学习粒子群算法。首先,以工件的最大完工时间、最大机器负荷和所有机器总负荷为优化目标建立了多目标柔性作业车间调度模型。然后,该算法结合多目标Pareto方法和教与同伴学习粒子群算法,采用快速非支配排序算法产生初始Pareto非支配解集,用提取Pareto支配层程序更新Pareto非支配解集,同时采用混合分派规则产生初始种群,采用开口向上抛物线递减的惯性权重选择策略提高算法的收敛速度。最后,对3个Benchmark算例进行仿真实验。理论分析和仿真表明,与带向导性局部搜索的多目标进化算法(MOEA-GLS)和带局部搜索的控制遗传算法(AL-CGA)相比,对于相同的测试实例,该算法能产生更多更好的Pareto非支配解;在计算时间方面,该算法要小于带向导性局部搜索的多目标进化算法。实验结果表明该算法可以有效解决多目标柔性作业车间调度问题。     

一种混合的多目标粒子群算法

将混沌变异和局部搜索与粒子群算法相结合用于多目标寻优。寻优的过程中以拥挤距离为标准,在进化的不同阶段采用相应的优化策略。当种群陷入局部最优时用混沌变异跳出该局部最优;用局部搜索法在进化后期增强算法的多样性和收敛性。实验结果表明,该方法求得的Pareto前沿分布更加均匀,更加接近理论的Pareto前沿。     

带时间窗车辆路径问题的多目标文化基因算法

针对物流配送中带时间窗的车辆路径问题,以最小化车辆使用数和行驶距离为目标,建立了多目标数学模型,提出了一种求解该问题的多目标文化基因算法。种群搜索采用遗传算法的进化模式和Pareto排序的选择方式,局部搜索采用禁忌搜索机制和存储池的结构,协调两者得到的Pareto非占优解的关系。与不带局部搜索的多目标遗传算法和单目标文化基因算法的对比实验表明,本文算法的求解质量较高。     

基于多种群差分进化的多目标优化算法

针对差分进化算法(Differential Evolution Algorithm,DE)求解多目标优化问题时易陷入局部最优的问题,设计了一种双向搜索机制,它通过对相反进化方向产生的两个子代个体进行评价,来增强DE算法的局部搜索能力;设计了多种群机制,它可令各子群独立进化一定次数再执行全局进化,以完成子群间进化信息的交流,这一方面降低了算法陷入局部最优的风险,另一方面增强了Pareto解集的多样性,使Pareto前沿面的解集分布更为均匀。实验结果表明,相比于NSGA-II等同类算法,所提方法在搜索Pareto最优解时效率更高,并且Pareto最优解集的精度及分布程度比前者更好。     

一种用于求解多目标组合优化的混合遗传算法 *

为高效求解多目标组合优化问题 ,提出一种进化计算与局部搜索结合的多目标算法。此算法基于个体排序数和密度值进行适应度赋值 ,采用非劣解并行局部搜索策略 ,在解的适应度赋值和局部搜索过程中使用 Pa-reto支配的概念。实验结果表明 ,新算法不仅提高了优化搜索的效率 ,且能够找到更多的近似 Pareto最优解。     

一种混合自适应多目标Memetic算法

Memetic算法是求解多目标优化问题最有效的方法之一，融合了局部搜索和进化计算，具有较高的全局搜索能力．混合自适应多目标Memetic算法（HAMA）用基于模拟退火的加权法进行局部搜索，采用Pareto法实现交叉和变异，通过扰动增强算法的exploration能力，且进化过程可根据改善率自适应调整，以提高搜索效率并改善算法的鲁棒性．算例测试说明HAMA能产生更接近Pareto前沿且多样性更好的近似集．     

基于GMOGSO的多目标流水车间调度问题

针对缓冲区有限的多目标流水车间调度问题, 提出一种基于Pareto 最优的广义多目标萤火虫算法. 通过引入交换子和交换序将基本萤火虫算法离散化, 并将算法拓展为全局搜索过程和局部搜索过程. 进化初期采用全局搜索将种群推向较优区域, 进化中后期采用捕食搜索策略使算法主体在全局搜索和局部搜索间智能切换, 从而保证全局与局部的平衡. 动态变步长策略进一步增强了算法搜索能力. 通过算例测试验证了所提出算法的有效性.

     

基于平衡搜索策略的多目标粒子群优化算法*

鉴于平衡全局和局部搜索在多目标粒子群优化算法获取完整均匀Pareto最优前沿方面的重要性,设计平衡全局和局部搜索策略,进而提出改进的多目标粒子群优化算法(bsMOPSO).文中策略在局部搜索方面设计归档集自挖掘子策略,通过对归档集中均匀分布的部分粒子进行柯西扰动,使归档集涵盖整个前沿面的局部搜索.在全局搜索方面设计边界最优粒子引导搜索子策略,以边界最优粒子替换部分粒子的全局最优解,引导粒子向各维目标的边界区域搜索.选取4种对比算法在ZDT和DTLZ系列的部分测试函数上进行实验,结果表明bsMOPSO具有更快的Pareto最优前沿收敛效率和更好的分布性.     

基于全局最优位置自适应选取与局部搜索的多目标粒子群优化算法

针对多目标粒子群优化算法全局最优位置〖BP(〗(gbest)〖BP)〗选取存在的缺陷和局部搜索能力弱的缺点,提出一种基于全局最优位置自适应选取与局部搜索的多目标粒子群优化算法MOPSO-GL。首先对Sigma法进行改进,引入拥挤距离机制,不再是粒子从档案中选择全局最优位置,而是档案成员从种群中选择合适的被引导粒子,引导种群均匀快速地向Pareto前沿飞行,提高了Pareto解的收敛性和多样性;其次当种群寻优能力减弱时,引入基于Skew Tent映射的变尺度全面搜索混沌优化策略对外部档案进行局部搜索,以提高算法的收敛性;最后通过与其他多目标优化算法的比较,结果表明MOPSO-GL具有更好的收敛性和分布性。     

变邻域遗传算法在车间物流调度中的应用

针对含有自动引导小车(Automated Guided Vehicle,AGV)的离散化车间物流调度问题,以最小化物流任务时间惩罚成本和最小化运载小车的总行驶距离为优化目标,构建离散化车间多目标物流调度优化模型,设计一种基于Pareto寻优的多目标混合变邻域搜索遗传算法(VNSGA-II).以遗传算法为基础,通过使用NSGA-II的Pareto分层和拥挤度计算方法评估种群优劣实现多目标优化,为了提高算法的寻优能力,避免算法陷入局部最优,通过添加保优记忆库对精英个体进行保护,并利用变邻域搜索算法在搜索过程中的局部寻优能力,针对本文模型特点,设计6个随机邻域结构,来达到算法求解最优值的目标.并提出了基于关键AGV小车的插入邻域和基于关键物流任务的交换邻域调整策略以进一步降低成本.最后,以某离散车间物流调度为实例,分别使用VNSGA-II、带精英策略的快速非支配排序遗传算法Ⅱ(Nondominated Sorting Genetic AlgorithmⅡ,NSGA-II)和强Pareto进化算法(Strong Pareto Evolutionary Algorithm 2,SPEA2)对问题进行求解,计算结果表明,VNSGA-II能得到更好的Pareto解集,验证了算法的有效性和可行性.     

HCS: A New Local Search Strategy for Memetic Multiobjective Evolutionary Algorithms

In this paper, we propose and investigate a new local search strategy for multiobjective memetic algorithms. More precisely, we suggest a novel iterative search procedure, known as the Hill Climber with Sidestep (HCS), which is designed for the treatment of multiobjective optimization problems, and show further two possible ways to integrate the HCS into a given evolutionary strategy leading to new memetic (or hybrid) algorithms. The pecularity of the HCS is that it is intended to be capable both moving toward and along the (local) Pareto set depending on the distance of the current iterate toward this set. The local search procedure utilizes the geometry of the directional cones of such optimization problems and works with or without gradient information. Finally, we present some numerical results on some well-known benchmark problems, indicating the strength of the local search strategy as a standalone algorithm as well as its benefit when used within a MOEA. For the latter we use the state of the art algorithms Nondominated Sorting Genetic Algorithm-II and Strength Pareto Evolutionary Algorithm 2 as base MOEAs.      

多目标混合进化算法求解加工时间可控的开放车间调度问题

开放车间调度问题属于典型的NP-hard问题。目前的相关研究大多假设工序在机器上具有固定的加工时间。然而,在大多数现实生产场景中,机床的加工时间可以通过调节加工功率加以控制。同时优化完工时间和总能耗两个冲突目标对高效、节能的开放车间生产具有重要意义。为此,研究了可控加工时间的多目标开放车间调度问题（MOOSPCPT）,以最小化完工时间和总额外能耗为目标构建了混合整数规划模型,并提出一种多目标混合进化算法（MOHEA）用于求解MOOSPCPT。在MOHEA中提出多个策略：1）改进生物地理学优化算法中的迁移策略和变异策略用于全局搜索,有效地提高了种群的多样性;2）基于关键路径设计一种自调整变邻域搜索策略,增强了算法的局部搜索能力;3）设计了一种加工时间重置算子,从而显著提升了算法的搜索效率。仿真实验结果表明：所提出的策略有效地提升了算法性能;相较于NSGA-Ⅱ（Non-dominated Sorting Genetic Algorithm Ⅱ）、NSGA-Ⅲ（Non-dominated Sorting Genetic Algorithm III）和SPEA2（Strength Pareto Evolutionary Algorithm 2）,MOHEA能够更有效地解决MOOSPCPT。     

基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题

柔性作业车间调度问题（FJSP）是一类应用广泛的组合优化问题。针对多目标FJSP求解过程复杂、算法易陷入局部最优的问题,提出了一种基于多区域采样策略的混合粒子群优化算法（HPSO-MRS）,以同时优化最大完工时间和总机器延迟时间这两个目标。多区域采样策略能够区分粒子所在Pareto前沿面的位置,根据不同区域进行采样重组,并为采样后位于Pareto前沿面多个区域的粒子规划相应的运动方向,从而有针对性地调整粒子在多个方向上的收敛能力,并带来一定程度的均匀分布能力的提升。此外,编解码方面使用带插空机制的解码策略来消除可能存在的局部左移;粒子更新方面将传统粒子群优化（PSO）算法的粒子更新方式与遗传算法（GA）的交叉变异算子相结合,提升了算法搜索过程的多样性并避免算法陷入局部最优。把所提算法在Benchmark问题Mk01~Mk10上进行测试,与传统的HPSO、NSGA-Ⅱ、基于适应度分配策略的多目标进化算法（SPEA2）和基于分解的多目标进化算法（MOEA/D）进行算法效力和运行效率对比。显著性分析的实验结果表明,HPSO-MRS在收敛性评价指标HV和IGD上分别在85%和77.5%的对照组中显著优于对比算法,而该算法在35%的对照组中的分布性指标Spacing显著优于对比算法,且均不存在所提算法显著差于对比算法的情况。可见相较于对比算法,所提出的算法具备较好的收敛与分布性能。     

Approximating the nondominated front using the Pareto Archived Evolution Strategy

We introduce a simple evolution scheme for multiobjective optimization problems, called the Pareto Archived Evolution Strategy (PAES). We argue that PAES may represent the simplest possible nontrivial algorithm capable of generating diverse solutions in the Pareto optimal set. The algorithm, in its simplest form, is a (1 + 1) evolution strategy employing local search but using a reference archive of previously found solutions in order to identify the approximate dominance ranking of the current and candidate solution vectors. (1 + 1)-PAES is intended to be a baseline approach against which more involved methods may be compared. It may also serve well in some real-world applications when local search seems superior to or competitive with population-based methods. We introduce (1 + lambda) and (mu + lambda) variants of PAES as extensions to the basic algorithm. Six variants of PAES are compared to variants of the Niched Pareto Genetic Algorithm and the Nondominated Sorting Genetic Algorithm over a diverse suite of six test functions. Results are analyzed and presented using techniques that reduce the attainment surfaces generated from several optimization runs into a set of univariate distributions. This allows standard statistical analysis to be carried out for comparative purposes. Our results provide strong evidence that PAES performs consistently well on a range of multiobjective optimization tasks.     

基于个体优化的自适应小生境遗传算法

针对遗传算法在处理复杂多峰函数优化问题时易于早熟和局部搜索能力差等问题,提出一种基于个体优化的自适应小生境遗传算法。在自适应小生境的基础上,利用进化过程中相邻个体的信息产生的试探点标记的算法进化方向,缩短邻域搜索的区间,提高算法的局部搜索能力。对复杂多峰问题进行的优化实验结果证明,该算法能快速可靠地收敛到全局最优解,其收敛速度和解精度均优于简单遗传算法和其他小生境算法。     

基于遗传粒子群算法的飞行冲突解脱

飞行冲突解脱是空中交通流量控制与优化调度中的难点。针对遗传算法求解多机飞行冲突存在搜索速度慢、易陷入局部最优与早熟收敛的问题,提出一种遗传粒子群算法解决多机飞行冲突。该算法综合遗传算法的全局搜索能力和粒子群算法的记忆功能与快速收敛特性,能够有效地解决遗传算法求解飞行冲突存在的不足。仿真验证了该算法能够得出较好的结果,无论是在搜索速度还是在求解精度上都有明显的提高。     

Perturbed Decomposition Algorithm applied to the multi-objective Traveling Salesman Problem

Dealing with multi-objective combinatorial optimization, this article proposes a new multi-objective set-based meta-heuristic named Perturbed Decomposition Algorithm (PDA). Combining ideas from decomposition methods, local search and data perturbation, PDA provides a 2-phase modular framework for finding an approximation of the Pareto front. The first phase decomposes the search into a number of linearly aggregated problems of the original multi-objective problem. The second phase conducts an iterative process: aggregated problems are first perturbed then selected and optimized by an efficient single-objective local search solver. Resulting solutions will serve as a starting point of a multi-objective local search procedure, called Pareto Local Search. After presenting a literature review of meta-heuristics on the multi-objective symmetric Traveling Salesman Problem (TSP), we conduct experiments on several instances of the bi-objective and tri-objective TSP. The experiments show that our proposed algorithm outperforms the best current methods on this problem.     

求解作业车间调度问题的混合帝国主义竞争算法

针对最小化最大完工时间的作业车间调度问题（JSP）,提出一种结合帝国主义竞争算法（ICA）和禁忌搜索（TS）算法的混合算法。混合算法以帝国主义竞争算法为基础,在同化操作中融入遗传算法中的杂交算子和变异算子,使算法全局搜索能力更强。为了克服帝国主义竞争算法局部搜索能力弱的缺点,引入禁忌搜索算法进一步优化同化操作后的后代。禁忌搜索算法采用混合邻域结构和新型选择策略,使得算法能够更有效地搜索邻域解。混合算法兼具全局搜索能力和局部搜索能力,通过对13个经典的Benchmark调度问题进行仿真测试,并与近年4种新型混合算法进行对比分析,实验结果表明了所提算法求解Job Shop调度问题的有效性和稳定性。     

An effective coding approach for multiobjective integrated resource selection and operation sequences problem

In this paper, we consider an integrated Resource Selection and Operation Sequences (iRS/OS) problem in Intelligent Manufacturing System (IMS). Several kinds of objectives are taken into account, in which the makespan for orders should be minimized; workloads among machine tools should be balanced; the total transition times between machines in a local plant should also be minimized. To solve this multiobjective iRS/OS model, a new two vectors-based coding approach has been proposed to improve the efficiency by designing a chromosome containing two kinds of information, i.e., operation sequences and machine selection. Using such kind of chromosome, we adapt multistage operation-based Genetic Algorithm (moGA) to find the Pareto optimal solutions. Moreover a special technique called left-shift hillclimber has been used as one kind of local search to improve the efficiency of our algorithm. Finally, the experimental results of several iRS/OS problems indicate that our proposed approach can obtain best solutions. Further more comparing with previous approaches, moGA performs better for finding Pareto solutions. Received: May 2005/Accepted: December 2005