Convergence analysis of a self-adaptive multi-objective evolutionary algorithm based on grids

Evolutionary algorithms have been successfully applied to various multi-objective optimization problems. However, theoretical studies on multi-objective evolutionary algorithms, especially with self-adaption, are relatively scarce. This paper analyzes the convergence properties of a self-adaptive (μ+1)-algorithm. The convergence of the algorithm is defined, and general convergence conditions are studied. Under these conditions, it is proven that the proposed self-adaptive (μ+1)-algorithm converges in probability or almost surely to the Pareto-optimal front.     

Convergence performance comparison of quantum-inspired multi-objective evolutionary algorithms

In recent research, we proposed a general framework of quantum-inspired multi-objective evolutionary algorithms (QMOEA) and gave one of its sufficient convergence conditions to the Pareto optimal set. In this paper, two Q-gate operators, H gate and R&N gate, are experimentally validated as two Q-gate paradigms meeting the convergence condition. The former is a modified rotation gate, and the latter is a combination of rotation gate and NOT gate with the specified probability. To investigate their effectiveness and applicability, several experiments on the multi-objective 0/1 knapsack problems are carried out. Compared to two typical evolutionary algorithms and the QMOEA only with rotation gate, the QMOEA with H gate and R&N gate have more powerful convergence ability in high complex instances. Moreover, the QMOEA with R&N gate has the best convergence in almost all of the experimental problems. Furthermore, the appropriate ε value regions for two Q-gates are verified.     

Dynamic multi-objective evolutionary algorithms for single-objective optimization

This paper proposes a new method for handling the difficulty of multi-modality for the single-objective optimization problem (SOP). The method converts a SOP to an equivalent dynamic multi-objective optimization problem (DMOP). A new dynamic multi-objective evolutionary algorithm (DMOEA) is implemented to solve the DMOP. The DMOP has two objectives: the original objective and a niche-count objective. The second objective aims to maintain the population diversity for handling the multi-modality difficulty during the search process. Experimental results show that the performance of the proposed algorithm is significantly better than the state-of-the-art competitors on a set of benchmark problems and real world antenna array problems.     

混合分解和强度帕累托多目标进化算法

在多目标进化优化中,使用分解策略的基于分解的多目标进化算法(MOEA/D)时间复杂度低,使用〖BP(〗强度帕累托策略的〖BP)〗强度帕累托进化算法-2(SPEA2)能得到分布均匀的解集。结合这两种策略,提出一种新的多目标进化算法用于求解具有复杂、不连续的帕累托前沿的多目标优化问题(MOP)。首先,利用分解策略快速逼近帕累托前沿;然后,利用强度帕累托策略使解集均匀分布在帕累托前沿,利用解集重置分解策略中的权重向量集,使其适配于特定的帕累托前沿;最后,利用分解策略进一步逼近帕累托前沿。使用的反向世代距离(IGD)作为度量标准,将新算法与MOEA/D、SPEA2和paλ-MOEA/D在12个基准问题上进行性能对比。实验结果表明该算法性能在7个基准问题上最优,在5个基准问题上接近于最优,且无论MOP的帕累托前沿是简单或复杂、连续或不连续的,该算法均能生成分布均匀的解集。     

Comparative analysis of multi-objective evolutionary algorithms for QoS-aware web service composition

Web service composition combines available services to provide new functionality. The various available services have different quality-of-service (QoS) attributes. Building a QoS-optimal web service composition is a multi-criteria NP-hard problem. Most of the existing approaches reduce this problem to a single-criterion problem by aggregating different criteria into a unique global score (scalarization). However, scalarization has some significant drawbacks: the end user is supposed to have a complete a priori knowledge of its preferences/constraints about the desired solutions and there is no guarantee that the aggregated results match it. Moreover, non-convex parts of the Pareto set cannot be reached by optimizing a convex weighted sum. An alternative is to use Pareto-based approaches that enable a more accurate selection of the end-user solution. However, so far, only few solutions based on these approaches have been proposed and there exists no comparative study published to date. This motivated us to perform an analysis of several state-of-the-art multi-objective evolutionary algorithms. Multiple scenarios with different complexities are considered. Performance metrics are used to compare several evolutionary algorithms. Results indicate that GDE3 algorithm yields the best performances on this problem, also with the lowest time complexity.     

The assessment of evolutionary algorithms for analyzing the positional accuracy and uncertainty of maps

Pre-geodetic maps are an important part of our cultural heritage and a potential source of information for historical studies. Historical cartography should be evaluated in terms of precision and uncertainty prior to their use in any application. In the last decade, the majority of papers that address multi-objective optimization employed the concept of Pareto optimality. The goal of Pareto-based multi-objective strategies is to generate a front (set) of nondominated solutions as an approximation to the true Pareto-optimal front. This article proposes a solution for the problems of multi-objective accuracy and uncertainty analysis of pre-geodetic maps using four Pareto-based multi-objective evolutionary algorithms: HVSEA, NSGAII, SPEAII and msPESA. “The Geographic Atlas of Spain (AGE)” by Tomas Lopez in 1804 provides the cartography for this study. The results obtained from the data collected from the kingdoms of Extremadura and Aragon, sheets of maps (54-55-56-57) and (70-71-72-73), respectively, demonstrate the advantages of these multi-objective approaches compared with classical methods. The results show that the removal of 8% of the towns it is possible to obtain improvements of approximately 30% for HVSEA, msPESA and NSGAII. The comparison of these algorithms indicates that the majority of nondominated solutions obtained by NSGAII dominate the solutions obtained by msPESA and HVSEA; however, msPESA and HVSEA obtain acceptable extreme solutions in some instances. The Pareto fronts based on multi-objective evolutionary algorithms (MOEAs) are a better alternative when the uncertainty of map analyzed is high or unknown. Consequently, Pareto-based multi-objective evolutionary algorithms establish new perspectives for analyzing the positional accuracy and uncertainty of maps.     

A multi-objective evolutionary algorithm to exploit the similarities of resource allocation problems

The complexity of a resource allocation problem (RAP) is usually NP-complete, which makes an exact method inadequate to handle RAPs, and encourages heuristic techniques to this class of problems for obtaining approximate solutions in polynomial time. Different heuristic techniques have already been investigated for handling various RAPs. However, since the properties of an RAP can help in characterizing other RAPs, instead of individual solution techniques, the similarities of different RAPs might be exploited for developing a common solution technique for them. Two RAPs of quite different nature, namely university class timetabling and land-use management, are considered here for such a study. The similarities between the problems are first explored, and then a common multi-objective evolutionary algorithm (a kind of heuristic techniques) for them is developed by exploiting those similarities. The algorithm is problem-dependent to some extent and can easily be extended to other similar RAPs. In the present work, the algorithm is applied to two real instances of the considered problems, and its properties are derived from the obtained results.     

基于遗传算法求解多目标优化问题Pareto前沿

该文给出了传统的求解多目标优化方法存在的问题,引入了当前研究多目标优化的新方法———基于遗传算法求解问题的pareto解,讨论了该方法要解决的关键问题———多样性保持及解决策略,并给出了一个求解pareto解集的新算法,算法简单、高效、鲁棒性强。最后给出了实验结果。     

Wind turbine selection for wind farm layout using multi-objective evolutionary algorithms

Wind energy has become the world’s fastest growing energy source. Although wind farm layout is a well known problem, its solution used to be heuristic, mainly based on the designer experience. A key in search trend is to increase power production capacity over time. Furthermore the production of wind energy often involves uncertainties due to the stochastic nature of wind speeds. The addressed problem contains a novel aspect with respect of other wind turbine selection problems in the context of wind farm design. The problem requires selecting two different wind turbine models (from a list of 26 items available) to minimize the standard deviation of the energy produced throughout the day while maximizing the total energy produced by the wind farm. The novelty of this new approach is based on the fact that wind farms are usually built using a single model of wind turbine. This paper describes the usage of multi-objective evolutionary algorithms (MOEAs) in the context of power energy production, selecting a combination of two different models of wind turbine along with wind speeds distributed over different time spans of the day. Several MOEAs variants belonging to the most renowned and widely used algorithms such as SPEA2 NSGAII, PESA and msPEA have been investigated, tested and compared based on the data gathered from Cancun (Mexico) throughout the year of 2008. We have demonstrated the powerful of MOEAs applied to wind turbine selection problem (WTS) and estimate the mean power and the associated standard deviation considering the wind speed and the dynamics of the power curve of the turbines. Among them, the performance of PESA algorithm looks a little bit superior than the other three algorithms. In conclusion, the use of MOEAs is technically feasible and opens new perspectives for assisting utility companies in developing wind farms.     

Multi-objective evolutionary algorithms for energy-aware scheduling on distributed computing systems

The ongoing increase of energy consumption by IT infrastructures forces data center managers to find innovative ways to improve energy efficiency. The latter is also a focal point for different branches of computer science due to its financial, ecological, political, and technical consequences. One of the answers is given by scheduling combined with dynamic voltage scaling technique to optimize the energy consumption. The way of reasoning is based on the link between current semiconductor technologies and energy state management of processors, where sacrificing the performance can save energy.This paper is devoted to investigate and solve the multi-objective precedence constrained application scheduling problem on a distributed computing system, and it has two main aims: the creation of general algorithms to solve the problem and the examination of the problem by means of the thorough analysis of the results returned by the algorithms.The first aim was achieved in two steps: adaptation of state-of-the-art multi-objective evolutionary algorithms by designing new operators and their validation in terms of performance and energy. The second aim was accomplished by performing an extensive number of algorithms executions on a large and diverse benchmark and the further analysis of performance among the proposed algorithms. Finally, the study proves the validity of the proposed method, points out the best-compared multi-objective algorithm schema, and the most important factors for the algorithms performance.     

求解多目标优化问题的一种多子群体进化算法

提出一种新的多目标粒子群优化（MOPSO）算法,根据多目标优化问题（MOP）的特点,将一个进化群体分成若干个子群体,利用非劣支配的概念构造全局最优区域,用以指导整个粒子群的进化．通过子群体间的信息交换．使整个群体分布更均匀,并且避免了局部最优,保证了解的多样性,通过很少的迭代次数便可得到分布均匀的Pareto有效解集．数值实验表明了该算法的有效性.     

Solving a dial-a-ride problem with a hybrid evolutionary multi-objective approach: Application to demand responsive transport

Demand responsive transport allows customers to be carried to their destination as with a taxi service, provided that the customers are grouped in the same vehicles in order to reduce operational costs. This kind of service is related to the dial-a-ride problem. However, in order to improve the quality of service, demand responsive transport needs more flexibility. This paper tries to address this issue by proposing an original evolutionary approach. In order to propose a set of compromise solutions to the decision-maker, this approach optimizes three objectives concurrently. Moreover, in order to intensify the search process, this multi-objective evolutionary approach is hybridized with a local search. Results obtained on random and realistic problems are detailed to compare three state-of-the-art algorithms and discussed from an operational point of view.     

多目标拆卸线平衡问题的Pareto细菌觅食算法*

拆卸线平衡问题的优化涉及多个目标,为克服传统方法在求解多目标拆卸线平衡问题时不能很好处理各子目标间冲突及易于早熟等不足,提出了一种多目标细菌觅食优化算法。算法采用Pareto非劣排序技术对种群进行分级,并结合拥挤距离机制评价同级个体的优劣。为提高算法收敛性能,在趋向性操作结束后引入精英保留策略保留优秀个体,并采用全局信息共享策略引导菌群不断向均匀分布的Pareto最优前沿趋近。通过不同规模算例的对比验证表明了算法的有效性与优越性。     

Improving the efficiency of multi-objective evolutionary algorithms through decomposition: An application to water distribution network design

Evolutionary algorithms (EAs) have been widely used in handling various water resource optimization problems in recent years. However, it is still challenging for EAs to identify near-optimal solutions for realistic problems within the available computational budgets. This paper introduces a novel multi-objective optimization method to improve the efficiency of a typically difficult water resource problem: water distribution network (WDN) design. In the proposed approach, a WDN is decomposed into different sub-networks using decomposition techniques. EAs optimize these sub-networks individually, generating Pareto fronts for each sub-network with great efficiency. A propagation method is proposed to evolve Pareto fronts of the sub-networks towards the Pareto front for the full network while eliminating the need to hydraulically simulate the intact network itself. Results from two complex realistic WDNs show that the proposed approach is able to find better fronts than conventional full-search algorithms (optimize the entire network without decomposition) with dramatically improved efficiency.     

Optimal fuzzy multi-criteria expansion of competence sets using multi-objectives evolutionary algorithms

Competence set is widely used to plan the optimal expansion process of skills, abilities or strategies. However, the conventional method is concerned only with one criterion rather than multi-criteria problems. In addition, the crisp value cannot reflect the ambiguity and the uncertainty in practice. In this paper, we propose the fuzzy criteria competence set analysis. In order to obtain Pareto solutions, multi-objective evolutionary algorithm (MOEA) is employed here. A numerical example with two fuzzy criteria is also used to illustrate the proposed method.     

Illustration of fairness in evolutionary multi-objective optimization

It is widely assumed that evolutionary algorithms for multi-objective optimization problems should use certain mechanisms to achieve a good spread over the Pareto front. In this paper, we examine such mechanisms from a theoretical point of view and analyze simple algorithms incorporating the concept of fairness. This mechanism tries to balance the number of offspring of all individuals in the current population. We rigorously analyze the runtime behavior of different fairness mechanisms and present illustrative examples to point out situations, where the right mechanism can speed up the optimization process significantly. We also indicate drawbacks for the use of fairness by presenting instances, where the optimization process is slowed down drastically.     

A multi-objective evolutionary algorithm for examination timetabling

This paper considers the scheduling of exams for a set of university courses. The solution to this exam timetabling problem involves the optimization of complete timetables such that there are as few occurrences of students having to take exams in consecutive periods as possible but at the same time minimizing the timetable length and satisfying hard constraints such as seating capacity and no overlapping exams. To solve such a multi-objective combinatorial optimization problem, this paper presents a multi-objective evolutionary algorithm that uses a variable-length chromosome representation and incorporates a micro-genetic algorithm and a hill-climber for local exploitation and a goal-based Pareto ranking scheme for assigning the relative strength of solutions. It also imports several features from the research on the graph coloring problem. The proposed algorithm is shown to be a more general exam timetabling problem solver in that it does not require any prior information of the timetable length to be effective. It is also tested against a few influential and recent optimization techniques and is found to be superior on four out of seven publicly available datasets.     

Three self-adaptive multi-objective evolutionary algorithms for a triple-objective project scheduling problem

Finding a Pareto-optimal frontier is widely favorable among researchers to model existing conflict objectives in an optimization problem. Project scheduling is a well-known problem in which investigating a combination of goals eventuate in a more real situation. Although there are many different types of objectives based on the situation on hand, three basic objectives are the most common in the literature of the project scheduling problem. These objectives are: (i) the minimization of the makespan, (ii) the minimization of the total cost associated with the resources, and (iii) the minimization of the variability in resources usage. In this paper, three genetic-based algorithms are proposed for approximating the Pareto-optimal frontier in project scheduling problem where the above three objectives are simultaneously considered. For the above problem, three self-adaptive genetic algorithms, namely (i) A two-stage multi-population genetic algorithm (MPGA), (ii) a two-phase subpopulation genetic algorithm (TPSPGA), and (iii) a non-dominated ranked genetic algorithm (NRGA) are developed. The algorithms are tested using a set of instances built from benchmark instances existing in the literature. The performances of the algorithms are evaluated using five performance metrics proposed in the literature. Finally according to the technique for order preference by similarity to ideal solution (TOPSIS) the self-adaptive NRGA gained the highest preference rank, followed by the self-adaptive TPSPGA and MPGA, respectively.     

An evolutionary approach for multi-objective vehicle routing problems with backhauls

The vehicle routing problem (VRP) is an important aspect of transportation logistics with many variants. This paper studies the VRP with backhauls (VRPB) in which the set of customers is partitioned into two subsets: linehaul customers requiring a quantity of product to be delivered, and backhaul customers with a quantity to be picked up. The basic VRPB involves finding a collection of routes with minimum cost, such that all linehaul and backhaul customers are serviced. A common variant is the VRP with selective backhauls (VRPSB), where the collection from backhaul customers is optional. For most real world applications, the number of vehicles, the total travel cost, and the uncollected backhauls are all important objectives to be minimized, so the VRPB needs to be tackled as a multi-objective problem. In this paper, a similarity-based selection evolutionary algorithm approach is proposed for finding improved multi-objective solutions for VRPB, VRPSB, and two further generalizations of them, with fully multi-objective performance evaluation.     

An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows

The vehicle routing problem with time windows is a complex combinatorial problem with many real-world applications in transportation and distribution logistics. Its main objective is to find the lowest distance set of routes to deliver goods, using a fleet of identical vehicles with restricted capacity, to customers with service time windows. However, there are other objectives, and having a range of solutions representing the trade-offs between objectives is crucial for many applications. Although previous research has used evolutionary methods for solving this problem, it has rarely concentrated on the optimization of more than one objective, and hardly ever explicitly considered the diversity of solutions. This paper proposes and analyzes a novel multi-objective evolutionary algorithm, which incorporates methods for measuring the similarity of solutions, to solve the multi-objective problem. The algorithm is applied to a standard benchmark problem set, showing that when the similarity measure is used appropriately, the diversity and quality of solutions is higher than when it is not used, and the algorithm achieves highly competitive results compared with previously published studies and those from a popular evolutionary multi-objective optimizer.