Enhancing Evolutionary Algorithms With Pattern Mining for Sparse Large-Scale Multi-Objective Optimization Problems

Sparse large-scale multi-objective optimization problems(SLMOPs)are common in science and engineering.However,the large-scale problem represents the high dimensionality of the decision space,requiring algorithms to traverse vast expanse with limited computational resources.Furthermore,in the context of sparse,most variables in Pareto optimal solutions are zero,making it difficult for algorithms to identify non-zero variables efficiently.This paper is dedicated to addressing the challenges posed by SLMOPs.To start,we introduce innovative objective functions customized to mine maximum and minimum candidate sets.This substantial enhancement dramatically improves the efficacy of frequent pattern mining.In this way,selecting candidate sets is no longer based on the quantity of nonzero variables they contain but on a higher proportion of nonzero variables within specific dimensions.Additionally,we unveil a novel approach to association rule mining,which delves into the intricate relationships between non-zero variables.This novel methodology aids in identifying sparse distributions that can potentially expedite reductions in the objective function value.We extensively tested our algorithm across eight benchmark problems and four real-world SLMOPs.The results demonstrate that our approach achieves competitive solutions across various challenges.

Multi-Objective Optimization Algorithm for Grouping Decision Variables Based on Extreme Point Pareto Frontier

The existing algorithms for solving multi-objective optimization problems fall into three main categories:Decomposition-based,dominance-based,and indicator-based.Traditional multi-objective optimization problemsmainly focus on objectives,treating decision variables as a total variable to solve the problem without consideringthe critical role of decision variables in objective optimization.As seen,a variety of decision variable groupingalgorithms have been proposed.However,these algorithms are relatively broad for the changes of most decisionvariables in the evolution process and are time-consuming in the process of finding the Pareto frontier.To solvethese problems,a multi-objective optimization algorithm for grouping decision variables based on extreme pointPareto frontier(MOEA-DV/EPF)is proposed.This algorithm adopts a preprocessing rule to solve the Paretooptimal solution set of extreme points generated by simultaneous evolution in various target directions,obtainsthe basic Pareto front surface to determine the convergence effect,and analyzes the convergence and distributioneffects of decision variables.In the later stages of algorithm optimization,different mutation strategies are adoptedaccording to the nature of the decision variables to speed up the rate of evolution to obtain excellent individuals,thusenhancing the performance of the algorithm.Evaluation validation of the test functions shows that this algorithmcan solve the multi-objective optimization problem more efficiently.

Tourism Route Recommendation Based on A Multi-Objective Evolutionary Algorithm Using Two-Stage Decomposition and Pareto Layering

Tourism route planning is widely applied in the smart tourism field.The Pareto-optimal front obtained by the traditional multi-objective evolutionary algorithm exhibits long tails,sharp peaks and disconnected regions problems,which leads to uneven distribution and weak diversity of optimization solutions of tourism routes.Inspired by these limitations,we propose a multi-objective evolutionary algorithm for tourism route recommendation(MOTRR)with two-stage and Pareto layering based on decomposition.The method decomposes the multiobjective problem into several subproblems,and improves the distribution of solutions through a two-stage method.The crowding degree mechanism between extreme and intermediate populations is used in the two-stage method.The neighborhood is determined according to the weight of the subproblem for crossover mutation.Finally,Pareto layering is used to improve the updating efficiency and population diversity of the solution.The two-stage method is combined with the Pareto layering structure,which not only maintains the distribution and diversity of the algorithm,but also avoids the same solutions.Compared with several classical benchmark algorithms,the experimental results demonstrate competitive advantages on five test functions,hypervolume(HV)and inverted generational distance(IGD)metrics.Using the experimental results of real scenic spot datasets from two famous tourism social networking sites with vast amounts of users and large-scale online comments in Beijing,our proposed algorithm shows better distribution.It proves that the tourism routes recommended by our proposed algorithm have better distribution and diversity,so that the recommended routes can better meet the personalized needs of tourists.

Hybrid Operator and Strengthened Diversity Improving for Multimodal Multi-Objective Optimization

Multimodal multi-objective optimization problems(MMOPs)contain multiple equivalent Pareto subsets(PSs)corresponding to a single Pareto front(PF),resulting in difficulty in maintaining promising diversities in both objective and decision spaces to find these PSs.Widely used to solve MMOPs,evolutionary algorithms mainly consist of evolutionary operators that generate new solutions and fitness evaluations of the solutions.To enhance performance in solving MMOPs,this paper proposes a multimodal multi-objective optimization evolutionary algorithm based on a hybrid operator and strengthened diversity improving.Specifically,a hybrid operator mechanism is devised to ensure the exploration of the decision space in the early stage and approximation to the optima in the latter stage.Moreover,an elitist-assisted differential evolution mechanism is designed for the early exploration stage.In addition,a new fitness function is proposed and used in environmental and mating selections to simultaneously evaluate diversities for PF and PSs.Experimental studies on 11 widely used benchmark instances from a test suite verify the superiority or at least competitiveness of the proposed methods compared to five state-of-the-art algorithms tailored for MMOPs.

Even Search in a Promising Region for Constrained Multi-Objective Optimization

In recent years, a large number of approaches to constrained multi-objective optimization problems(CMOPs) have been proposed, focusing on developing tweaked strategies and techniques for handling constraints. However, an overly finetuned strategy or technique might overfit some problem types,resulting in a lack of versatility. In this article, we propose a generic search strategy that performs an even search in a promising region. The promising region, determined by obtained feasible non-dominated solutions, possesses two general properties.First, the constrained Pareto front(CPF) is included in the promising region. Second, as the number of feasible solutions increases or the convergence performance(i.e., approximation to the CPF) of these solutions improves, the promising region shrinks. Then we develop a new strategy named even search,which utilizes the non-dominated solutions to accelerate convergence and escape from local optima, and the feasible solutions under a constraint relaxation condition to exploit and detect feasible regions. Finally, a diversity measure is adopted to make sure that the individuals in the population evenly cover the valuable areas in the promising region. Experimental results on 45 instances from four benchmark test suites and 14 real-world CMOPs have demonstrated that searching evenly in the promising region can achieve competitive performance and excellent versatility compared to 11 most state-of-the-art methods tailored for CMOPs.

Constrained Multi-Objective Optimization With Deep Reinforcement Learning Assisted Operator Selection

Solving constrained multi-objective optimization problems with evolutionary algorithms has attracted considerable attention.Various constrained multi-objective optimization evolutionary algorithms(CMOEAs)have been developed with the use of different algorithmic strategies,evolutionary operators,and constraint-handling techniques.The performance of CMOEAs may be heavily dependent on the operators used,however,it is usually difficult to select suitable operators for the problem at hand.Hence,improving operator selection is promising and necessary for CMOEAs.This work proposes an online operator selection framework assisted by Deep Reinforcement Learning.The dynamics of the population,including convergence,diversity,and feasibility,are regarded as the state;the candidate operators are considered as actions;and the improvement of the population state is treated as the reward.By using a Q-network to learn a policy to estimate the Q-values of all actions,the proposed approach can adaptively select an operator that maximizes the improvement of the population according to the current state and thereby improve the algorithmic performance.The framework is embedded into four popular CMOEAs and assessed on 42 benchmark problems.The experimental results reveal that the proposed Deep Reinforcement Learning-assisted operator selection significantly improves the performance of these CMOEAs and the resulting algorithm obtains better versatility compared to nine state-of-the-art CMOEAs.

A Survey of Evolutionary Algorithms for Multi-Objective Optimization Problems With Irregular Pareto Fronts

Evolutionary algorithms have been shown to be very successful in solving multi-objective optimization problems(MOPs).However,their performance often deteriorates when solving MOPs with irregular Pareto fronts.To remedy this issue,a large body of research has been performed in recent years and many new algorithms have been proposed.This paper provides a comprehensive survey of the research on MOPs with irregular Pareto fronts.We start with a brief introduction to the basic concepts,followed by a summary of the benchmark test problems with irregular problems,an analysis of the causes of the irregularity,and real-world optimization problems with irregular Pareto fronts.Then,a taxonomy of the existing methodologies for handling irregular problems is given and representative algorithms are reviewed with a discussion of their strengths and weaknesses.Finally,open challenges are pointed out and a few promising future directions are suggested.

Multi-objective Evolutionary Algorithms for MILP and MINLP in Process Synthesis

Steady-state non-dominated sorting genetic algorithm (SNSGA), a new form of multi-objective genetic algorithm, is implemented by combining the steady-state idea in steady-state genetic algorithms (SSGA) and the fitness assignment strategy of non-dominated sorting genetic algorithm (NSGA). The fitness assignment strategy is improved and a new self-adjustment scheme of is proposed. This algorithm is proved to be very efficient both computationally and in terms of the quality of the Pareto fronts produced with five test problems including GA difficult problem and GA deceptive one. Finally, SNSGA is introduced to solve multi-objective mixed integer linear programming (MILP) and mixed integer non-linear programming (MINLP) problems in process synthesis.

Solving material distribution routing problem in mixed manufacturing systems with a hybrid multi-objective evolutionary algorithm

The material distribution routing problem in the manufacturing system is a complex combinatorial optimization problem and its main task is to deliver materials to the working stations with low cost and high efficiency. A multi-objective model was presented for the material distribution routing problem in mixed manufacturing systems, and it was solved by a hybrid multi-objective evolutionary algorithm (HMOEA). The characteristics of the HMOEA are as follows: 1) A route pool is employed to preserve the best routes for the population initiation; 2) A specialized best?worst route crossover (BWRC) mode is designed to perform the crossover operators for selecting the best route from Chromosomes 1 to exchange with the worst one in Chromosomes 2, so that the better genes are inherited to the offspring; 3) A route swap mode is used to perform the mutation for improving the convergence speed and preserving the better gene; 4) Local heuristics search methods are applied in this algorithm. Computational study of a practical case shows that the proposed algorithm can decrease the total travel distance by 51.66%, enhance the average vehicle load rate by 37.85%, cut down 15 routes and reduce a deliver vehicle. The convergence speed of HMOEA is faster than that of famous NSGA-II.

Optimal setting and placement of FACTS devices using strength Pareto multi-objective evolutionary algorithm

This work proposes a novel approach for multi-type optimal placement of flexible AC transmission system(FACTS) devices so as to optimize multi-objective voltage stability problem. The current study discusses a way for locating and setting of thyristor controlled series capacitor(TCSC) and static var compensator(SVC) using the multi-objective optimization approach named strength pareto multi-objective evolutionary algorithm(SPMOEA). Maximization of the static voltage stability margin(SVSM) and minimizations of real power losses(RPL) and load voltage deviation(LVD) are taken as the goals or three objective functions, when optimally locating multi-type FACTS devices. The performance and effectiveness of the proposed approach has been validated by the simulation results of the IEEE 30-bus and IEEE 118-bus test systems. The proposed approach is compared with non-dominated sorting particle swarm optimization(NSPSO) algorithm. This comparison confirms the usefulness of the multi-objective proposed technique that makes it promising for determination of combinatorial problems of FACTS devices location and setting in large scale power systems.

A Multi-Objective Optimal Evolutionary Algorithm Based on Tree-Ranking

Multi-objective optimal evolutionary algorithms (MOEAs) are a kind of new effective algorithms to solve Multi-objective optimal problem (MOP). Because ranking, a method which is used by most MOEAs to solve MOP, has some shortcoming s, in this paper, we proposed a new method using tree structure to express the relationship of solutions. Experiments prove that the method can reach the Pare-to front, retain the diversity of the population, and use less time.

Do Search and Selection Operators Play Important Roles in Multi-Objective Evolutionary Algorithms:A Case Study

Multi-objective Evolutionary Algorithm (MOEA) is becoming a hot research area and quite a few aspects of MOEAs have been studied and discussed. However there are still few literatures discussing the roles of search and selection operators in MOEAs. This paper studied their roles by solving a case of discrete Multi-objective Optimization Problem (MOP): Multi-objective TSP with a new MOEA. In the new MOEA, We adopt an efficient search operator, which has the properties of both crossover and mutation, to generate the new individuals and chose two selection operators: Family Competition and Population Competition with probabilities to realize selection. The simulation experiments showed that this new MOEA could get good uniform solutions representing the Pareto Front and outperformed SPEA in almost every simulation run on this problem. Furthermore, we analyzed its convergence property using finite Markov chain and proved that it could converge to Pareto Front with probability 1. We also find that the convergence property of MOEAs has much relationship with search and selection operators.

Synergetic Optimization of Missile Shapes for Aerodynamic and Radar Cross-Section Performance Based on Multi-objective Evolutionary Algorithm

A multiple-objective evolutionary algorithm (MOEA) with a new Decision Making (DM) scheme for MOD of conceptual missile shapes was presented, which is contrived to determine suitable tradeoffs from Pareto optimal set using interactive preference articulation. There are two objective functions, to maximize ratio of lift to drag and to minimize radar cross-section (RCS) value. 3D computational electromagnetic solver was used to evaluate RCS, electromagnetic performance. 3D Navier-Stokes flow solver was adopted to evaluate aerodynamic performance. A flight mechanics solver was used to analyze the stability of the missile. Based on the MOEA, a synergetic optimization of missile shapes for aerodynamic and radar cross-section performance is completed. The results show that the proposed approach can be used in more complex optimization case of flight vehicles.

EFFICIENT MULTI-OBJECTIVE EVOLUTIONARY ALGORITHM FOR JOB SHOP SCHEDULING

A new representation method is first presented based on priority roles. According to this method, each entry in the chromosome indicates that in the procedure of the Giffler and Thompson （GT） algorithm, the conflict occurring in the corresponding machine is resolved by the corresponding priority role. Then crowding-measure multi-objective evolutionary algorithm （CMOEA） is designed, in which both archive maintenance and fitness assignment use crowding measure. Finally the comparisons between CMOEA and SPEA in solving 15 scheduling problems demonstrate that CMOEA is suitable to job shop scheduling.

An improved multi-objective optimization algorithm for solving flexible job shop scheduling problem with variable batches

In order to solve the flexible job shop scheduling problem with variable batches,we propose an improved multiobjective optimization algorithm,which combines the idea of inverse scheduling.First,a flexible job shop problem with the variable batches scheduling model is formulated.Second,we propose a batch optimization algorithm with inverse scheduling in which the batch size is adjusted by the dynamic feedback batch adjusting method.Moreover,in order to increase the diversity of the population,two methods are developed.One is the threshold to control the neighborhood updating,and the other is the dynamic clustering algorithm to update the population.Finally,a group of experiments are carried out.The results show that the improved multi-objective optimization algorithm can ensure the diversity of Pareto solutions effectively,and has effective performance in solving the flexible job shop scheduling problem with variable batches.

Evolutionary Multi/Many-Objective Optimisation via Bilevel Decomposition

Decomposition of a complex multi-objective optimisation problem(MOP)to multiple simple subMOPs,known as M2M for short,is an effective approach to multi-objective optimisation.However,M2M facilitates little communication/collaboration between subMOPs,which limits its use in complex optimisation scenarios.This paper extends the M2M framework to develop a unified algorithm for both multi-objective and manyobjective optimisation.Through bilevel decomposition,an MOP is divided into multiple subMOPs at upper level,each of which is further divided into a number of single-objective subproblems at lower level.Neighbouring subMOPs are allowed to share some subproblems so that the knowledge gained from solving one subMOP can be transferred to another,and eventually to all the subMOPs.The bilevel decomposition is readily combined with some new mating selection and population update strategies,leading to a high-performance algorithm that competes effectively against a number of state-of-the-arts studied in this paper for both multiand many-objective optimisation.Parameter analysis and component analysis have been also carried out to further justify the proposed algorithm.

Solving A Kind of High Complexity Multi-Objective Problems by A Fast Algorithm

A fast algorithm is proposed to solve a kind of high complexity multi-objective problems in this paper. It takes advantages of both the orthogonal design method to search evenly, and the statistical optimal method to speed up the computation. It is very suitable for solving high complexity problems, and quickly yields solutions which converge to the Pareto-optimal set with high precision and uniform distribution. Some complicated multi-objective problems are solved by the algorithm and the results show that the algorithm is not only fast but also superior to other MOGAS and MOEAs, such as the currently efficient algorithm SPEA, in terms of the precision, quantity and distribution of solutions.

基于改进MOEA/D的模糊柔性作业车间调度算法

针对实际生产车间中加工时间的不确定性,将加工时间以模糊数的形式表示,建立以最小化模糊最大完工时间和模糊总材料消耗为优化目标的多目标模糊柔性作业车间调度问题数学模型,提出一种改进基于分解的多目标进化算法(IMOEA/D)进行求解。该算法基于机器和工序两层编码并采用混合的初始化策略提高初始种群的质量,利用插入式贪婪解码策略对机器的选择进行解码,缩短总加工时间;采用基于邻域和外部存档的选择操作结合改进的交叉变异算子进行种群更新,提高搜索效率;设置邻域搜索的启动条件,并基于4种邻域动作进行变邻域搜索,提高局部搜索能力;通过田口实验设计方法研究关键参数对算法性能的影响,同时得到算法的最优性能参数。在Xu 1~Xu 2、Lei 1~Lei 4和Remanu 1~Remanu 4测试集上将所提算法与其他算法进行对比,结果表明,IMOEA/D算法的解集数量和目标函数值均较优,在Lei 2算例获得的解集个数为对比算法的2倍以上。

基于改进MOEA/D的车联网通信资源分配算法

为获得车联网通信资源分配的最优解,提出一种基于改进MOEA/D的车联网通信资源分配优化算法。将车联网资源请求的阻塞率和资源请求成功的总成本这2个相互冲突的网络通信资源分配要素作为网络通信资源分配的2个优化目标,根据车联网中行驶车辆的特点,对请求资源车辆和提供资源车辆设置约束条件。在此基础上,采用自适应邻域策略平衡进化过程中种群的收敛性和分布性,并将迭代次数引入自适应度,调节交叉算子和变异算子,使种群中较差的个体也具有遗传性,从而保证种群的多样性。同时,随着迭代次数的增加,种群中较差个体遗传性降低,较好个体遗传能力增强,从而保证种群的优化。仿真结果表明,该算法针对最小化阻塞率和最小化成本这2个目标能够获得满意的优化效果,在迭代次数、车辆数和资源请求数变化情况下都存在最优解,在相同迭代次数下,与基于支配的多目标算法SPEA2和NSGA-II相比具有较低的阻塞率和较好的收敛性。

Multi-objective evolutionary optimization for hardware-aware neural network pruning

Neural network pruning is a popular approach to reducing the computational complexity of deep neural networks.In recent years,as growing evidence shows that conventional network pruning methods employ inappropriate proxy metrics,and as new types of hardware become increasingly available,hardware-aware network pruning that incorporates hardware characteristics in the loop of network pruning has gained growing attention,Both network accuracy and hardware efficiency(latency,memory consumption,etc.)are critical objectives to the success of network pruning,but the conflict between the multiple objectives makes it impossible to find a single optimal solution.Previous studies mostly convert the hardware-aware network pruning to optimization problems with a single objective.In this paper,we propose to solve the hardware-aware network pruning problem with Multi-Objective Evolutionary Algorithms(MOEAs).Specifically,we formulate the problem as a multi-objective optimization problem,and propose a novel memetic MOEA,namely HAMP,that combines an efficient portfoliobased selection and a surrogate-assisted local search,to solve it.Empirical studies demonstrate the potential of MOEAs in providing simultaneously a set of alternative solutions and the superiority of HAMP compared to the state-of-the-art hardware-aware network pruning method.