Survey on ant colony optimization algorithms for stochastic combinatorial optimization
0
Citation
0
Reference
20
Related Paper
Abstract:
The optimization problem under uncertainty because of its closer to the real world environment,thus have become a growing reasearch area recently. This paper thoroughly reviewed ant colony optimization algorithms,and their applications to the class of stochastic combinatorial optimization problems under uncertainty conditions. Firstly,introduced the conceptual classification model for combinatorial problems under uncertainty conditions and a general definition for the stochastic combina-torial optimization problem. Then,pointed out the main difference between stochastic combinatorial optimization problem and deterministic combinatorial optimization problem,that was the computation of the objective function under uncertainty,and then summarized the current solutions for solvins this problem. Finally,proposed several possible research directions and the expectations of the development in this area.Keywords:
Extremal optimization
Robust Optimization
Cite
Cite
Citations (126)
Cardinality (data modeling)
Penalty Method
Cite
Citations (62)
We consider function optimization as a sequential decision making problem under the budget constraint. Such constraint limits the number of objective function evaluations allowed during the optimization. We consider an algorithm inspired by a continuous version of a multi-armed bandit problem which attacks this optimization problem by solving the tradeoff between exploration (initial quasi-uniform search of the domain) and exploitation (local optimization around the potentially global maxima). We introduce the so-called Simultaneous Optimistic Optimization (SOO), a deterministic algorithm that works by domain partitioning. The benefit of such an approach are the guarantees on the returned solution and the numerical efficiency of the algorithm. We present this machine learning rooted approach to optimization, and provide the empirical assessment of SOO on the CEC'2014 competition on single objective real-parameter numerical optimization testsuite.
Constrained optimization
Cite
Citations (34)
The facility layout problem is usually treated as a deterministic problem and uncertainty regarding problem parameters has seldom been addressed. This study aims to investigate different ways of dealing with uncertainty to design a facility layout which attains robust and efficient performance under a finite number of possible scenarios. For this purpose, several mathematical models based on the quadratic assignment problem (QAP) formulation are developed. These formulations cover alternative approaches in stochastic programming and robust optimization literature such as: minimizing expected cost, maximum cost and maximum regret. Proposed models are solved using genetic algorithms incorporating operators and schemes that are specially selected and adapted for the models. Finally, a novel approach, where the optimization problem under scenario-based uncertainty is transformed into a multi-objective optimization problem by considering each scenario as a separate objective, is proposed. By solving the multi-objective counterpart of scenario-based QAP (mQAP), optimal solutions with respect to different robust performance measures can be obtained simultaneously in a Pareto optimal set. A multi-objective evolutionary algorithm is developed to solve the mQAP. Extensive numerical analysis enables comparison of the performance of these approaches and provides important insights about dealing with uncertainty in the facility layout problem.
Robust Optimization
Cite
Citations (10)
An real world engineering design problem is usually with multiple conflicting objectives, and it is easily lead to the difficulty to optimize these objectives at the same time. Multiobjective combinatorial optimization is not only an open theory problem, but also with an important practical significance. After modeling the constrained multiobjective combinatorial optimization problem, a new optimization algorithm is presented in detail. The algorithm is different from existing multiobjective evolutionary algorithms in three aspects. The first is the two-layer encoding method. The second is that it hybrids the simulated annealing algorithm with the genetic algorithm to improve the global searching ability while maintaining the parallel computing ability. The third is the decision making mechanism to evaluate candidate solutions with several design objectives. A numerical example study shows that the proposed algorithm is capable of dealing with multiobjective combinatorial optimization problems.
Algorithm design
Cite
Citations (5)
Cite
Citations (346)
Solver
Decision maker
Binary search algorithm
Cite
Citations (3)
Vehicle Routing Problem
Cite
Citations (3)
Pareto optimal
Cite
Citations (456)
From a kind of problems such as network design and transportation scheduling,a class of stochastic multiple-objectives optimization models have been formulated,in which there are one quaduatic and one linear objective functions and several linear constraints.We converted multiple-objectives optimization problems into a single-objective optimization problem based on the expectation level of Decision-Maker.The deterministic equivalent formulation was obtained by a new approach,called hybrid method of variance and expectation.Then,an interactive algorithm was developed,which reflected the preferences of Decision-Maker.Numerical experiments showed that the proposed new method is prior to the existing method both in reflecting the satisfaction degree of Decision-Maker and in obtaining a robust solution.
Decision maker
Robust Optimization
Cite
Citations (1)