一种基于模拟退火的多目标Memetic算法

为了改善多目标进化算法的搜索效率，提出了基于模拟退火的多目标Memetic算法．此算法根据Pareto占优关系评价个体适应值，采用模拟退火进行局部搜索，并结合交叉算子和基于网格密度的选择机制改善算法的收敛速度和解的均衡分布．flowshop调度问题算例的仿真结果表明，基于模拟退火的多目标Memetic算法能够产生更接近Pareto前沿的近似集．     

基于新模型的多目标Memetic算法及收敛分析

将多目标函数优化问题转化成单目标约束优化问题.对转化后的问题提出了基于约束主导原理的选择方法,克服了多数方法只使用Pareto优胜关系作为选择策略而没有采用偏好信息这一缺陷;Memetic算法是求解多目标优化问题最有效的方法之一,它融合了局部搜索和进化计算.新的多目标Memetic算法引进C-metric,将模拟退火算法与遗传算法结合起米,改善了全局搜索能力.用概率论的有关知识证明了算法的收敛性.仿真结果表明该方法对不同的试验函数均可求出一组沿着Pareto前沿分布均匀且散布广泛的非劣解.     

基于自适应学习的多目标粒子群优化算法

将进化算法应用于某些多目标优化问题时,采用增加种群规模和进化代数的方法往往耗费大量的目标函数计算开销,且达不到提高种群进化效率的目的,为此提出了一种基于自适应学习最优搜索方向的多目标粒子群优化算法。采用自适应惯性权值平衡算法的全局和局部搜索能力,采用聚类排挤方法保持Pareto非支配解集的分布均匀性,使用最近邻学习方法为每个粒子在Pareto非支配解集中寻找一个最优飞行目标来提高其收敛速度并保持粒子群搜索方向的多样性。实验结果表明,提出的算法可在显著地降低函数评估成本的前提下实现快速的搜索,并使粒子群均匀地逼近Pareto最优面。     

一种新的基于进化策略的多目标优化算法

用进化策略求解多目标优化问题时,为了提高解在决策变量空间中的搜索能力和保证Pareto前沿的多样性,提出了一种新的基于进化策略的多目标优化算法。运用自适应变异步长的进化策略,使解在决策变量空间中进行全局和局部搜索;并引入非劣解按一定比例进入下一代的方法,使完全被占优的个体有机会参与到下一代的繁殖,保持了解在Pareto前沿的多样性。该算法在保证解在决策空间多样性的同时,也保持了Pareto前沿的多样性。仿真实验表明,该算法具有良好的搜索性能。     

一种基于云模型的多目标进化算法

在多目标进化算法的基础上,提出了一种基于云模型的多目标进化算法(CMOEA).算法设计了一种新的变异算子来自适应地调整变异概率,使得算法具有良好的局部搜索能力.算法采用小生境技术,其半径按X条件云发生器非线性动态地调整以便于保持解的多样性,同时动态计算个体的拥挤距离并采用云模型参数来估计个体的拥挤度,逐个删除种群中超出的非劣解以保持解的分布性.将该算法用于多目标0/1背包问题来测试CMOEA的性能,并与目前最流行且有效的多目标进化算法NSGA-II及SPEA2进行了比较.结果表明,CMOEA具有良好的搜索性能,并能很好地维持种群的多样性,快速收敛到Pareto前沿,所获得的Pareto最优解集具有更好的收敛性与分布性.     

求解多目标问题的Memetic免疫优化算法

将基于Pareto支配关系的局部下山算子和差分算子引入免疫多目标优化算法之中,提出了一种求解多目标问题的Memetic免疫优化算法(Memetic immune algorithm for multiobjective optimization,简称MIAMO).该算法利用种群中抗体在决策空间上的位置关系设计了两种有效的启发式局部搜索策略,提高了免疫多目标优化算法的求解效率.仿真实验结果表明,MIAMO与其他4种有效的多目标优化算法相比,不仅在求得Pareto最优解集的逼近性、均匀性和宽广性上有明显优势,而且算法的收敛速度与免疫多目标优化算法相比明显加快.     

一种自适应多目标离散差分进化算法

提出一种自适应多目标离散差分进化算法。该算法将差分进化引入多目标优化领域,采用一种新的自适应离散差分进化策略增强算法的全局搜索能力,以获得更优的Pareto近似解,并结合Pareto快速分层排序策略和基于聚集密度的按层修剪操作对种群进行更新维护,使解集保持良好的多样性。实例测试和算法比较表明,该算法能有效求解离散域和连续域上不同类型的多目标优化问题,且在收敛性、分布性、稳定性方面均表现较好。     

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

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

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

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

基于自适应进化学习的约束多目标粒子群优化算法

针对约束边界粒子在边界区域搜索能力不足的问题,提出一种基于自适应进化学习的约束多目标粒子群优化算法。该算法根据不符合约束条件粒子的约束违反程度,修正优化算法的进化学习公式,提高算法在约束边界区域的搜索能力;通过引入一种基于拥挤距离的Pareto最优解分布性动态维护策略,在不增加算法复杂度的前提下改进Pareto前沿的分布性。实验结果表明,所提出的算法可以获得具有更好收敛性、分布性和多样性的Pareto前沿。     

一种求解多目标组合优化的遗传局部搜索算法

为改善遗传算法求解多目标组合优化问题的搜索效率,提出一种新的遗传局部搜索算法.算法采取非劣解并行局部搜索策略以及基于分散度的精英选择策略,并采用基于NSGA-Ⅱ的适应度赋值方式和二元赌轮选择操作,以提高算法收敛性,保持群体多样性.实验结果表明,新算法能够产生数量较多分布较广的近似Pareto最优解.     

基于动态拥挤距离的混合多目标免疫优化算法

多目标免疫优化算法的研究目标是种群均匀分布于优化问题的非劣最优域并使算法快速收敛。为进一步提高多目标优化问题非支配解集合的分布均匀性和收敛性,提出了一种基于动态拥挤距离的混合多目标免疫优化算法。该算法基于动态拥挤距离来对个体进行比较和更新操作,从而保持最终解集的均匀分布,同时借鉴经典差分进化算法中的变异引导算子来加强免疫优化算法的局部搜索能力并提高搜索精度。基于5个经典测试函数的仿真结果表明, 与其他几种有效的多目标优化算法相比,所提算法不仅在求得Pareto最优解集的逼近性、均匀性和宽广性上有明显优势,而且收敛速度也有较大的改进和提高。     

Multi-objective genetic local search algorithm using Kohonen’s neural map

Genetic Algorithms (GAs) are population based global search methods that can escape from local optima traps and find the global optima regions. However, near the optimum set their intensification process is often inaccurate. This is because the search strategy of GAs is completely probabilistic. With a random search near the optimum sets, there is a small probability to improve current solution. Another drawback of the GAs is genetic drift. The GAs search process is a black box process and no one knows that which region is being searched by the algorithm and it is possible that GAs search only a small region in the feasible space. On the other hand, GAs usually do not use the existing information about the optimality regions in past iterations.In this paper, a new method called SOM-Based Multi-Objective GA (SBMOGA) is proposed to improve the genetic diversity. In SBMOGA, a grid of neurons use the concept of learning rule of Self-Organizing Map (SOM) supporting by Variable Neighborhood Search (VNS) learn from genetic algorithm improving both local and global search. SOM is a neural network which is capable of learning and can improve the efficiency of data processing algorithms. The VNS algorithm is developed to enhance the local search efficiency in the Evolutionary Algorithms (EAs). The SOM uses a multi-objective learning rule based-on Pareto dominance to train its neurons. The neurons gradually move toward better fitness areas in some trajectories in feasible space. The knowledge of optimum front in past generations is saved in form of trajectories. The final state of the neurons determines a set of new solutions that can be regarded as the probability density distribution function of the high fitness areas in the multi-objective space. The new set of solutions potentially can improve the GAs overall efficiency. In the last section of this paper, the applicability of the proposed algorithm is examined in developing optimal policies for a real world multi-objective multi-reservoir system which is a non-linear, non-convex, multi-objective optimization problem.     

基于改进多目标布谷鸟搜索的资源调度算法

针对IaaS(Infrastructure as a Service)云计算中资源调度的多目标优化问题,提出一种基于改进多目标布谷鸟搜索的资源调度算法。在多目标布谷鸟搜索算法的基础上,通过改进随机游走策略和丢弃概率策略提高了算法的局部搜索能力和收敛速度。以最大限度地减少完成时间和成本为主要目标,将任务分配特定的VM(Virtual Manufacturing)满足云用户对云提供商的资源利用的需求,从而减少延迟,提高资源利用率和服务质量。实验结果表明,该算法可以有效地解决IaaS云计算环境中资源调度的多目标问题,与其他算法相比,具有一定的优势。     

Attributed multi-objective comprehensive learning particle swarm optimization for optimal security of networks

In particle swarm optimization (PSO) each particle uses its personal and global or local best positions by linear summation. However, it is very time consuming to find the global or local best positions in case of complex problems. To overcome this problem, we propose a new multi-objective variant of PSO called attributed multi-objective comprehensive learning particle swarm optimizer (A-MOCLPSO). In this technique, we do not use global or local best positions to modify the velocity of a particle; instead, we use the best position of a randomly selected particle from the whole population to update the velocity of each dimension. This method not only increases the speed of the algorithm but also searches in more promising areas of the search space. We perform an extensive experimentation on well-known benchmark problems such as Schaffer (SCH), Kursawa (KUR), and Zitzler–Deb–Thiele (ZDT) functions. The experiments show very convincing results when the proposed technique is compared with existing versions of PSO known as multi-objective comprehensive learning particle swarm optimizer (MOCLPSO) and multi-objective particle swarm optimization (MOPSO), as well as non-dominated sorting genetic algorithm II (NSGA-II). As a case study, we apply our proposed A-MOCLPSO algorithm on an attack tree model for the security hardening problem of a networked system in order to optimize the total security cost and the residual damage, and provide diverse solutions for the problem. The results of our experiments show that the proposed algorithm outperforms the previous solutions obtained for the security hardening problem using NSGA-II, as well as MOCLPSO for the same problem. Hence, the proposed algorithm can be considered as a strong alternative to solve multi-objective optimization problems.     

A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems

This paper presents a new, carefully designed algorithm for five bi-objective permutation flow shop scheduling problems that arise from the pairwise combinations of the objectives (i) makespan, (ii) the sum of the completion times of the jobs, and (iii) both, the weighted and non-weighted total tardiness of all jobs. The proposed algorithm combines two search methods, two-phase local search and Pareto local search, which are representative of two different, but complementary, paradigms for multi-objective optimization in terms of Pareto-optimality. The design of the hybrid algorithm is based on a careful experimental analysis of crucial algorithmic components of these two search methods. We compared our algorithm to the two best algorithms identified, among a set of 23 candidate algorithms, in a recent review of the bi-objective permutation flow-shop scheduling problem. We have reimplemented carefully these two algorithms in order to assess the quality of our algorithm. The experimental comparison in this paper shows that the proposed algorithm obtains results that often dominate the output of the two best algorithms from the literature. Therefore, our analysis shows without ambiguity that the proposed algorithm is a new state-of-the-art algorithm for the bi-objective permutation flow-shop problems studied in this paper.     

A multi-objective genetic algorithm for mixed-model assembly line rebalancing

When demand structure or production technology changes, a mixed-model assembly line (MAL) may have to be reconfigured to improve its efficiency in the new production environment. In this paper, we address the rebalancing problem for a MAL with seasonal demands. The rebalancing problem concerns how to reassign assembly tasks and operators to candidate stations under the constraint of a given cycle time. The objectives are to minimize the number of stations, workload variation at each station for different models, and rebalancing cost. A multi-objective genetic algorithm (moGA) is proposed to solve this problem. The genetic algorithm (GA) uses a partial representation technique, where only a part of the decision information about a candidate solution is expressed in the chromosome and the rest is computed optimally. A non-dominated ranking method is used to evaluate the fitness of each chromosome. A local search procedure is developed to enhance the search ability of moGA. The performance of moGA is tested on 23 reprehensive problems and the obtained results are compared with those by other authors.     

Clear and smooth path planning

One of the challenging problems in motion planning is finding an efficient path for a robot in different aspects such as length, clearance and smoothness. We formulate this problem as two multi-objective path planning models with the focus on robot's energy consumption and path's safety. These models address two five- and three-objectives optimization problems. We propose an evolutionary algorithm for solving the problems. For efficient searching and achieving Pareto-optimal regions, in addition to the standard genetic operators, a family of path refiner operators is introduced. The new operators play a local search role and intensify power of the algorithm in both explorative and exploitative terms. Finally, we verify the models and compare efficiency of the algorithm and the refiner operators by other multi-objective algorithms such as strength Pareto evolutionary algorithm 2 and multi-objective particle swarm optimization on several complicated path planning test problems.     

A machine-learning based memetic algorithm for the multi-objective permutation flowshop scheduling problem

In recent years, the historical data during the search process of evolutionary algorithms has received increasing attention from many researchers, and some hybrid evolutionary algorithms with machine-learning have been proposed. However, the majority of the literature is centered on continuous problems with a single optimization objective. There are still a lot of problems to be handled for multi-objective combinatorial optimization problems. Therefore, this paper proposes a machine-learning based multi-objective memetic algorithm (ML-MOMA) for the discrete permutation flowshop scheduling problem. There are two main features in the proposed ML-MOMA. First, each solution is assigned with an individual archive to store the non-dominated solutions found by it and based on these individual archives a new population update method is presented. Second, an adaptive multi-objective local search is developed, in which the analysis of historical data accumulated during the search process is used to adaptively determine which non-dominated solutions should be selected for local search and how the local search should be applied. Computational results based on benchmark problems show that the cooperation of the above two features can help to achieve a balance between evolutionary global search and local search. In addition, many of the best known Pareto fronts for these benchmark problems in the literature can be improved by the proposed ML-MOMA.     

Memory-based adaptive partitioning (MAP) of search space for the enhancement of convergence in Pareto-based multi-objective evolutionary algorithms

A new algorithm, dubbed memory-based adaptive partitioning (MAP) of search space, which is intended to provide a better accuracy/speed ratio in the convergence of multi-objective evolutionary algorithms (MOEAs) is presented in this work. This algorithm works by performing an adaptive-probabilistic refinement of the search space, with no aggregation in objective space. This work investigated the integration of MAP within the state-of-the-art fast and elitist non-dominated sorting genetic algorithm (NSGAII). Considerable improvements in convergence were achieved, in terms of both speed and accuracy. Results are provided for several commonly used constrained and unconstrained benchmark problems, and comparisons are made with standalone NSGAII and hybrid NSGAII-efficient local search (eLS).