求解约束优化问题的混合粒子群算法

针对约束优化问题提出一种混合粒子群求解算法,该算法根据可行性规则,引入自适应惩罚函数,结合模拟退火算法,不断地寻找更优可行解,逐渐达到搜索全局最优解.通过对一些标准函数测试,计算机仿真结果表明,该方法是有效和可行的,且具有较高的计算精度,相比传统算法,最优解精度达到10-15.     

Pareto Optimal Microwave Filter Design Using Multiobjective Differential Evolution

Microwave filters play an important role in modern wireless communications. A novel method for the design of multilayer dielectric and open loop ring resonator (OLRR) filters under constraints is presented. The proposed design method is based on generalized differential evolution (GDE3), which is a multiobjective extension of differential evolution (DE). GDE3 algorithm can be applied for global optimization to any engineering problem with an arbitrary number of objective and constraint functions. GDE3 is compared against other evolutionary multiobjective algorithms like nondominated sorting genetic algorithm-II (NSGA-II), multiobjective particle swarm optimization (MOPSO) and multiobjective particle swarm optimization with fitness sharing (MOPSO-fs) for a number of microwave filter design cases. In the multilayer dielectric filter design case a predefined database of low loss dielectric materials is used. The results indicate the advantages of this approach and the applicability of this design method.      

Designing resilient networks using multicriteria metaheuristics

The paper deals with the design of resilient networks that are fault tolerant against link failures. Usually, fault tolerance is achieved by providing backup paths, which are used in case of an edge failure on a primary path. We consider this task as a multiobjective optimization problem: to provide resilience in networks while minimizing the cost subject to capacity constraint. We propose a stochastic approach, which can generate multiple Pareto solutions in a single run. The feasibility of the proposed method is illustrated by considering several network design problems using a single weighted average of objectives and a direct multiobjective optimization approach using the Pareto dominance concept.     

Materialized view selection as constrained evolutionary optimization

One of the important issues in data warehouse development is the selection of a set of views to materialize in order to accelerate a large number of on-line analytical processing (OLAP) queries. The maintenance-cost view-selection problem is to select a set of materialized views under certain resource constraints for the purpose of minimizing the total query processing cost. However, the search space for possible materialized views may be exponentially large. A heuristic algorithm often has to be used to find a near optimal solution. In this paper, for the maintenance-cost view-selection problem, we propose a new constrained evolutionary algorithm. Constraints are incorporated into the algorithm through a stochastic ranking procedure. No penalty functions are used. Our experimental results show that the constraint handling technique, i.e., stochastic ranking, can deal with constraints effectively. Our algorithm is able to find a near-optimal feasible solution and scales with the problem size well.     

Pareto-Based Multiobjective Machine Learning: An Overview and Case Studies

Machine learning is inherently a multiobjective task. Traditionally, however, either only one of the objectives is adopted as the cost function or multiple objectives are aggregated to a scalar cost function. This can be mainly attributed to the fact that most conventional learning algorithms can only deal with a scalar cost function. Over the last decade, efforts on solving machine learning problems using the Pareto-based multiobjective optimization methodology have gained increasing impetus, particularly due to the great success of multiobjective optimization using evolutionary algorithms and other population-based stochastic search methods. It has been shown that Pareto-based multiobjective learning approaches are more powerful compared to learning algorithms with a scalar cost function in addressing various topics of machine learning, such as clustering, feature selection, improvement of generalization ability, knowledge extraction, and ensemble generation. One common benefit of the different multiobjective learning approaches is that a deeper insight into the learning problem can be gained by analyzing the Pareto front composed of multiple Pareto-optimal solutions. This paper provides an overview of the existing research on multiobjective machine learning, focusing on supervised learning. In addition, a number of case studies are provided to illustrate the major benefits of the Pareto-based approach to machine learning, e.g., how to identify interpretable models and models that can generalize on unseen data from the obtained Pareto-optimal solutions. Three approaches to Pareto-based multiobjective ensemble generation are compared and discussed in detail. Finally, potentially interesting topics in multiobjective machine learning are suggested.     

基于多目标进化策略算法的DNA核酸编码设计

设计高质量的核酸分子集合能有效提高DNA计算的可靠性、有效性和可求解问题的规模。DNA分子需要满足热力学约束、相似度约束、GC含量约束等多个相互冲突的目标函数,是典型的多目标优化问题。该文提出一种多目标进化策略(MOES)算法求解DNA分子序列设计问题,算法设计了随机碱基变异算子实现高效的局部搜索和全局搜索。改进的评价函数综合考虑了候选解的支配关系和冲突目标的平衡程度,选取符合DNA编码约束的核酸序列。实验结果证明,该文提出的算法具有高效的搜索效率和快速收敛能力,可以产生高质量的DNA序列集合,优于其他对比算法产生的DNA分子序列集合。     

Geometrical Design of Plate-Fin Heat Sinks Using Hybridization of MOEA and RSM

The work in this paper is aimed at demonstrating the practical multiobjective optimization of plate-fin heat sinks and the superiority of using a combined response surface method and multiobjective evolutionary optimizer over solely using the evolutionary optimizer. The design problem assigned is to minimize a heat sink junction temperature and fan pumping power. Design variables determine a heat sink geometry and inlet air velocity. Design constraints are given in such a way that the maximum and minimum fin heights are properly limited. Function evaluation is carried out by using finite volume analysis software. Two multiobjective evolutionary optimization strategies, real-code strength Pareto evolutionary algorithm with and without the use of a response surface technique, are implemented to explore the Pareto optimal front. The optimum results obtained from both design approaches are compared and discussed. It is illustrated that the multiobjective evolutionary technique is a powerful tool for the multiobjective design of electronic air-cooled heat sinks. With the same design conditions and an equal number of function evaluations, the multiobjective optimizer in association with the response surface technique totally outperforms the other. The design parameters affecting the diversity of the Pareto front include fin thickness, fin height distribution, and inlet air velocity while the plate base thickness and the total number of fins of the non-dominated solutions tend to approach certain values.     

Multiobjective placement of electronic components using evolutionary algorithms

The optimal placement of electronic components on a printed circuit board is a well-studied optimization task. However, despite the involvement of multiple conflicting objectives, researchers have mainly used a single objective of minimizing the overall wire length or minimizing the overall heat generation or minimizing the overall time delay in its functioning. In this paper, the problem is treated as a two-objective optimization problem of minimizing the overall wire length and minimizing the failure-rate of the board arising due to uneven local heat accumulation. The proposed strategy uses a novel representation procedure and a multiobjective evolutionary algorithm capable of finding multiple Pareto-optimal solutions simultaneously. Moreover, the flexibility and efficacy of the proposed strategy have been demonstrated by simultaneously optimizing the placement of components and the layout of the board. The convergence and the extent of spread obtained in the solutions reliably by repetitive applications of the proposed procedure should encourage further application of the approach to more complex placement design problems.     

Penalty function-based joint diagonalization approach for convolutive blind separation of nonstationary sources

A new approach for convolutive blind source separation (BSS) by explicitly exploiting the second-order nonstationarity of signals and operating in the frequency domain is proposed. The algorithm accommodates a penalty function within the cross-power spectrum-based cost function and thereby converts the separation problem into a joint diagonalization problem with unconstrained optimization. This leads to a new member of the family of joint diagonalization criteria and a modification of the search direction of the gradient-based descent algorithm. Using this approach, not only can the degenerate solution induced by a unmixing matrix and the effect of large errors within the elements of covariance matrices at low-frequency bins be automatically removed, but in addition, a unifying view to joint diagonalization with unitary or nonunitary constraint is provided. Numerical experiments are presented to verify the performance of the new method, which show that a suitable penalty function may lead the algorithm to a faster convergence and a better performance for the separation of convolved speech signals, in particular, in terms of shape preservation and amplitude ambiguity reduction, as compared with the conventional second-order based algorithms for convolutive mixtures that exploit signal nonstationarity.     

A penalty function semi-continuous thresholding methods for constraints of hashing problems

The Hashing process is an effective tool for handling large-scale data (for example, images, videos, or multi-model data) retrieval problems. To get better retrieval accuracy, hashing models usually are imposed with three rigorous constraints, i.e., discrete binary constraint, uncorrelated condition, and the balanced constraint, which will lead to being ‘NP-hard’. In this study, we divide the whole constraints set into the uncorrelated (orthogonality) constraint and the binary discrete balance constraint and propose a fast and accurate penalty function semi-continuous thresholding (PFSCT) hash coding algorithm based on forward–backward algorithms. In addition, we theoretically analyze the equivalence between the relaxed model and the original problems. Extensive numerical experiments on diverse large-scale benchmark datasets demonstrate comparable performance and effectiveness of the proposed method.     

An evolutionary approach to designing complex spreading codes for DS-CDMA

This paper proposes a novel evolutionary approach to spreading code design in direct sequence code division multiple access (DS-CDMA). Specifically, a multiobjective evolutionary algorithm (EA) is used to generate complex spreading sequences that are optimized with respect to the average mean-square cross- and/or autocorrelation (CC and/or AC) properties. A theoretical model is developed in order to demonstrate the optimality of the generated codes. The proposed algorithm enables spreading code design with no constraints on the code length. Furthermore, it is possible to generate K/spl ges/N codes of length N with very little cost in correlation properties. This results in significant capacity enhancement in DS-CDMA systems.     

一种基于多样性信息和收敛度的多目标粒子群优化算法

为了提高多目标粒子群算法优化解的多样性和收敛性,提出了一种基于多样性信息和收敛度的多目标粒子群优化算法（Multiobjective Particle Swarm Optimization based on the Diversity Information and Convergence Degree,dicdMOPSO）.首先,利用非支配解多样性信息评估知识库中最优解的分布状态,设计出一种全局最优解选择机制,平衡了种群的进化过程,提高了非支配解的多样性和收敛性;其次,基于种群多样性信息设计出一种飞行参数调整机制,增强了粒子的全局探索能力和局部开发能力,获得了多样性和收敛性较好的种群.最后,将dicdMOPSO应用于标准测试函数测试,实验结果表明,dicdMOPSO与其他多目标算法相比不仅获得了多样性较高的可行解,而且能够较快的收敛到Pareto前沿.     

Multiobjective evolutionary algorithm for the optimization of noisy combustion processes

This work introduces a multiobjective evolutionary algorithm capable of handling noisy problems with a particular emphasis on robustness against unexpected measurements (outliers). The algorithm is based on the Strength Pareto evolutionary algorithm of Zitzler and Thiele and includes the new concepts of domination dependent lifetime, re-evaluation of solutions and modifications in the update of the archive population. Several tests on prototypical functions underline the improvements in convergence speed and robustness of the extended algorithm. The proposed algorithm is implemented to the Pareto optimization of the combustion process of a stationary gas turbine in an industrial setup. The Pareto front is constructed for the objectives of minimization of NO/sub x/ emissions and reduction of the pressure fluctuations (pulsation) of the flame. Both objectives are conflicting affecting the environment and the lifetime of the turbine, respectively. The optimization leads a Pareto front corresponding to reduced emissions and pulsation of the burner. The physical implications of the solutions are discussed and the algorithm is evaluated.     

Performance analysis of minimum variance CDMA receivers

Constrained optimization of the receiver's output variance has previously been proposed as a relatively simple method for designing blind multiuser detectors for DS-CDMA systems. A single constraint is sufficient for the AWGN case, whereas multiple constraints should be used in a multipath environment. It is shown in this paper that the choice of the constraint parameters in the multipath case can have a significant effect on the system performance. A max/min approach for optimizing the constraint is proposed, resulting in blind solutions with improved performance. It is shown that the performance of the proposed method tends to be close to that of the MMSE receiver at high SNR, whereas the constraint parameters converge to the multipath channel parameters. The proposed method does not require knowledge of the interfering users' codes and timing. Simulation results support those performance claims     

基于博弈策略的能效优化的子载波分配方法

本文引入显示当前子载波质量的信道状态矩阵,以系统总功耗、单个子载波上的功耗、总时延、干扰温度限和单个子载波上的次用户数等为约束条件,以能效为目标函数,建立多约束条件下的分式规划机制.设计演化博弈算子,为每个次用户建立效用函数,当每个次用户的效用函数达到最优时,演化博弈达到Nash均衡点,此时的策略组合认为是能效相对最优的资源分配状态.通过实验仿真对比,本文给出的EESA-EG（Energy Efficient Subcarrier Allocation withEvolutionary Game）算法的能效相对最优,且给出了相对最为合理的子载波分配方案,为信道状态更优的子载波分配了更多的子载波.     

A Survey of Evolutionary Algorithms for Clustering

This paper presents a survey of evolutionary algorithms designed for clustering tasks. It tries to reflect the profile of this area by focusing more on those subjects that have been given more importance in the literature. In this context, most of the paper is devoted to partitional algorithms that look for hard clusterings of data, though overlapping (i.e., soft and fuzzy) approaches are also covered in the paper. The paper is original in what concerns two main aspects. First, it provides an up-to-date overview that is fully devoted to evolutionary algorithms for clustering, is not limited to any particular kind of evolutionary approach, and comprises advanced topics like multiobjective and ensemble-based evolutionary clustering. Second, it provides a taxonomy that highlights some very important aspects in the context of evolutionary data clustering, namely, fixed or variable number of clusters, cluster-oriented or nonoriented operators, context-sensitive or context-insensitive operators, guided or unguided operators, binary, integer, or real encodings, centroid-based, medoid-based, label-based, tree-based, or graph-based representations, among others. A number of references are provided that describe applications of evolutionary algorithms for clustering in different domains, such as image processing, computer security, and bioinformatics. The paper ends by addressing some important issues and open questions that can be subject of future research.      

基于精确罚函数法的遗传算法求解时延约束组播路由问题

有时延约束的组播问题是通信网络多点路由优化问题中的重要部分,已被证明是NP-complete问题.本文提出了一种基于罚函数法的启发式遗传算法以求解该问题,并讨论了违反时延约束不可行解的罚函数选取问题,进化过程中采用适于此类问题的动态交配概率、变异概率以提高算法的收敛速度.最后分析了算法的复杂度.仿真表明,本文算法是有效的、稳定的.     

Optimal apportionment of reliability and redundancy in seriessystems under multiple objectives

A multiobjective reliability apportionment problem for a series system with time-dependent reliability is presented. The resulting mathematical programming formulation determines the optimal level of component reliability and the number of redundant components at each stage. The problem is a multiobjective, nonlinear, mixed-integer mathematical programming problem, subject to several design constraints. Sequential unconstrained minimization techniques in conjunction with heuristic algorithms are used to find an optimum solution. A generalization of the problem in view of inherent vagueness in the objective and the constraint functions results in an ill-structured reliability apportionment problem. This multiobjective fuzzy optimization problem is solved using nonlinear programming. The computational procedure is illustrated through a numerical example. The fuzzy optimization techniques can be useful during initial stages of the conceptual design of engineering systems where the design goals and design constraints have not been clearly identified or stated, and for decision making problems in ill-structured situations     

自适应分解式多目标粒子群优化算法

为了提高多目标粒子群优化算法解的分布性,文中提出了一种自适应分解式多目标粒子群优化算法（Adaptive Multiobjective Particle Swarm Optimization based on Decomposed Archive,AMOPSO-DA）.首先,设计了一种基于优化解空间分布信息的外部档案更新策略,有效提升了AMOPSO-DA的空间搜索能力;其次,提出了一种基于粒子进化方向信息的飞行参数调整方法,有效平衡了AMOPSO-DA的探索和开发能力.最后,将提出的AMOPSO-DA应用于多目标优化问题,实验结果表明,文中提出的AMOPSO-DA能够获得分布性较好的优化解.     

Optimization and FROC analysis of rule-based detection schemes using a multiobjective approach

Computerized detection schemes have the potential of increasing diagnostic accuracy in medical imaging by alerting radiologists to lesions that they initially overlooked. These schemes typically employ multiple parameters such as threshold values or filter weights to arrive at a detection decision. In order for the system to have high performance, the values of these parameters need to be set optimally. Conventional optimization techniques are designed to optimize a scalar objective function. The task of optimizing the performance of a computerized detection scheme, however, is clearly a multiobjective problem: we wish to simultaneously improve the sensitivity and false-positive rate of the system. In this work we investigate a multiobjective approach to optimizing computerized rule-based detection schemes. In a multiobjective optimization, multiple objectives are simultaneously optimized, with the objective now being a vector-valued function. The multiobjective optimization problem admits a set of solutions, known as the Pareto-optimal set, which are equivalent in the absence of any information regarding the preferences of the objectives. The performances of the Pareto-optimal solutions can be interpreted as operating points on an optimal free-response receiver operating characteristic (FROC) curve, greater than or equal to the points on any possible FROC curve for a given dataset and detection scheme. It is demonstrated that generating FROC curves in this manner eliminates several known problems with conventional FROC curve generation techniques for rule-based detection schemes. We employ the multiobjective approach to optimize a rule-based scheme for clustered microcalcification detection that has been developed in our laboratory.