Multi-objective genetic algorithm for solving N-version program design problem

N-version programming (NVP) is a programming approach for constructing fault tolerant software systems. Generally, an optimization model utilized in NVP selects the optimal set of versions for each module to maximize the system reliability and to constrain the total cost to remain within a given budget. In such a model, while the number of versions included in the obtained solution is generally reduced, the budget restriction may be so rigid that it may fail to find the optimal solution. In order to ameliorate this problem, this paper proposes a novel bi-objective optimization model that maximizes the system reliability and minimizes the system total cost for designing N-version software systems. When solving multi-objective optimization problem, it is crucial to find Pareto solutions. It is, however, not easy to obtain them. In this paper, we propose a novel bi-objective optimization model that obtains many Pareto solutions efficiently.We formulate the optimal design problem of NVP as a bi-objective 0–1 nonlinear integer programming problem. In order to overcome this problem, we propose a Multi-objective genetic algorithm (MOGA), which is a powerful, though time-consuming, method to solve multi-objective optimization problems. When implementing genetic algorithm (GA), the use of an appropriate genetic representation scheme is one of the most important issues to obtain good performance. We employ random-key representation in our MOGA to find many Pareto solutions spaced as evenly as possible along the Pareto frontier. To pursue improve further performance, we introduce elitism, the Pareto-insertion and the Pareto-deletion operations based on distance between Pareto solutions in the selection process.The proposed MOGA obtains many Pareto solutions along the Pareto frontier evenly. The user of the MOGA can select the best compromise solution among the candidates by controlling the balance between the system reliability and the total cost.     

Multi-objective scheduling problems: Determination of pruned Pareto sets

There are often multiple competing objectives for industrial scheduling and production planning problems. Two practical methods are presented to efficiently identify promising solutions from among a Pareto optimal set for multi-objective scheduling problems. Generally, multi-objective optimization problems can be solved by combining the objectives into a single objective using equivalent cost conversions, utility theory, etc., or by determination of a Pareto optimal set. Pareto optimal sets or representative subsets can be found by using a multi-objective genetic algorithm or by other means. Then, in practice, the decision maker ultimately has to select one solution from this set for system implementation. However, the Pareto optimal set is often large and cumbersome, making the post-Pareto analysis phase potentially difficult, especially as the number of objectives increase. Our research involves the post Pareto analysis phase, and two methods are presented to filter the Pareto optimal set to determine a subset of promising or desirable solutions. The first method is pruning using non-numerical objective function ranking preferences. The second approach involves pruning by using data clustering. The k-means algorithm is used to find clusters of similar solutions in the Pareto optimal set. The clustered data allows the decision maker to have just k general solutions from which to choose. These methods are general, and they are demonstrated using two multi-objective problems involving the scheduling of the bottleneck operation of a printed wiring board manufacturing line and a more general scheduling problem.     

An improved robust buffer allocation method for the project scheduling problem

Unpredictable uncertainties cause delays and additional costs for projects. Often, when using traditional approaches, the optimizing procedure of the baseline project plan fails and leads to delays. In this study, a two-stage multi-objective buffer allocation approach is applied for robust project scheduling. In the first stage, some decisions are made on buffer sizes and allocation to the project activities. A set of Pareto-optimal robust schedules is designed using the meta-heuristic non-dominated sorting genetic algorithm (NSGA-II) based on the decisions made in the buffer allocation step. In the second stage, the Pareto solutions are evaluated in terms of the deviation from the initial start time and due dates. The proposed approach was implemented on a real dam construction project. The outcomes indicated that the obtained buffered schedule reduces the cost of disruptions by 17.7% compared with the baseline plan, with an increase of about 0.3% in the project completion time.     

A new multi-objective optimization model for preventive maintenance and replacement scheduling of multi-component systems

In this article, a new multi-objective optimization model is developed to determine the optimal preventive maintenance and replacement schedules in a repairable and maintainable multi-component system. In this model, the planning horizon is divided into discrete and equally-sized periods in which three possible actions must be planned for each component, namely maintenance, replacement, or do nothing. The objective is to determine a plan of actions for each component in the system while minimizing the total cost and maximizing overall system reliability simultaneously over the planning horizon. Because of the complexity, combinatorial and highly nonlinear structure of the mathematical model, two metaheuristic solution methods, generational genetic algorithm, and a simulated annealing are applied to tackle the problem. The Pareto optimal solutions that provide good tradeoffs between the total cost and the overall reliability of the system can be obtained by the solution approach. Such a modeling approach should be useful for maintenance planners and engineers tasked with the problem of developing recommended maintenance plans for complex systems of components.     

Robust structural damage identification based on multi‐objective optimization

Inverse analysis for structural damage identification often involves an optimization process that minimizes the discrepancies between the computed responses and the measured responses. Conventional single‐objective optimization approach defines the objective function by combining multiple error terms into a single one, which leads to a weaker constraint in solving the identification problem. A multi‐objective approach is proposed, which minimizes multiple error terms simultaneously. Its non‐domination‐based convergence provides a stronger constraint that enables robust identification of damages with lower false‐negative detection rate. Another merit of the proposed approach is quantified confidence in damage detection through processing Pareto‐optimal solutions. Numerical examples that simulate static testing are provided to compare the proposed approach with conventional formulation based on single‐objective optimization. Copyright © 2009 John Wiley & Sons, Ltd.     

A TABOO SEARCH BASED APPROACH TO FIND THE PARETO OPTIMAL SET IN MULTIPLE OBJECTIVE OPTIMIZATION

Taboo search is a heuristic optimization technique which works with a neighbourhood of solutions to optimize a given objective function. It is generally applied to single objective optimization problems. Taboo search has the potential for solving multiple objective optimization (MOO) problems, because it works with more than one solution at a time, and this gives it the opportunity to evaluate multiple objective functions simultaneously. In this paper, a taboo search based algorithm is developed to find Pareto optimal solutions in multiple objective optimization problems. The developed algorithm has been tested with a number of problems and compared with other techniques. Results obtained from this work have proved that a taboo search based algorithm can find Pareto optimal solutions in MOO effectively.     

基于差异演化算法和多属性决策的机电系统可靠性多目标优化设计

针对机电系统可靠性设计问题,以可靠性和费用(或体积等)最优为目标建立可靠性设计的多目标优化模型.提出了自适应多目标差异演化算法,该算法提出了自适应缩放因子和混沌交叉率,采用改进的快速排序方法构造Pareto最优解,采用NSGA-Ⅱ的拥挤操作对档案文件进行消减.采用自适应多目标差异演化算法获得多目标问题的Pareto最优...     

基于NSGA-Ⅱ的多目标代码混淆模型研究

为解决工业工程中的代码混淆领域存在的多种代码评价指标冲突，以及如何相应确定最优代码混淆技术应用序列的问题，基于NSGA-II遗传优化算法，建立一种面向多目标优化的代码混淆模型。提出了基于抽象语法树（AST）的树型基因编码，设计了适用于代码混淆的交叉、变异和选择操作。优化和选取多种可能发生冲突的软件复杂度组成广覆盖面指标集合作为NSGA-II的目标函数。应用多种具有代表性的代码混淆技术，设计了多套不同目标种类和不同目标个数的实验方案对该模型进行了有效性验证。     

Determination of Pareto frontier in multi-objective maintenance optimization

The objective of a maintenance policy generally is the global maintenance cost minimization that involves not only the direct costs for both the maintenance actions and the spare parts, but also those ones due to the system stop for preventive maintenance and the downtime for failure. For some operating systems, the failure event can be dangerous so that they are asked to operate assuring a very high reliability level between two consecutive fixed stops. The present paper attempts to individuate the set of elements on which performing maintenance actions so that the system can assure the required reliability level until the next fixed stop for maintenance, minimizing both the global maintenance cost and the total maintenance time. In order to solve the previous constrained multi-objective optimization problem, an effective approach is proposed to obtain the best solutions (that is the Pareto optimal frontier) among which the decision maker will choose the more suitable one. As well known, describing the whole Pareto optimal frontier generally is a troublesome task. The paper proposes an algorithm able to rapidly overcome this problem and its effectiveness is shown by an application to a case study regarding a complex series-parallel system.     

Practical solutions for multi-objective optimization: An application to system reliability design problems

For multiple-objective optimization problems, a common solution methodology is to determine a Pareto optimal set. Unfortunately, these sets are often large and can become difficult to comprehend and consider. Two methods are presented as practical approaches to reduce the size of the Pareto optimal set for multiple-objective system reliability design problems. The first method is a pseudo-ranking scheme that helps the decision maker select solutions that reflect his/her objective function priorities. In the second approach, we used data mining clustering techniques to group the data by using the k-means algorithm to find clusters of similar solutions. This provides the decision maker with just k general solutions to choose from. With this second method, from the clustered Pareto optimal set, we attempted to find solutions which are likely to be more relevant to the decision maker. These are solutions where a small improvement in one objective would lead to a large deterioration in at least one other objective. To demonstrate how these methods work, the well-known redundancy allocation problem was solved as a multiple objective problem by using the NSGA genetic algorithm to initially find the Pareto optimal solutions, and then, the two proposed methods are applied to prune the Pareto set.