Metaheuristic methods in hybrid flow shop scheduling problem

Memetic algorithms are hybrid evolutionary algorithms that combine global and local search by using an evolutionary algorithm to perform exploration while the local search method performs exploitation. This paper presents two hybrid heuristic algorithms that combine particle swarm optimization (PSO) with simulated annealing (SA) and tabu search (TS), respectively. The hybrid algorithms were applied on the hybrid flow shop scheduling problem. Experimental results reveal that these memetic techniques can effectively produce improved solutions over conventional methods with faster convergence.     

Evolutionary Approaches to Figure-Ground Separation

The problem of figure-ground separation is tackled from the perspective of combinatorial optimization. Previous attempts have used deterministic optimization techniques based on relaxation and gradient descent-based search, and stochastic optimization techniques based on simulated annealing and microcanonical annealing. A mathematical model encapsulating the figure-ground separation problem that makes explicit the definition of shape in terms of attributes such as cocircularity, smoothness, proximity and contrast is described. The model is based on the formulation of an energy function that incorporates pairwise interactions between local image features in the form of edgels and is shown to be isomorphic to the interacting spin (Ising) system from quantum physics. This paper explores a class of stochastic optimization techniques based on evolutionary algorithms for the problem of figure-ground separation. A class of hybrid evolutionary stochastic optimization algorithms based on a combination of evolutionary algorithms, simulated annealing and microcanonical annealing are shown to exhibit superior performance when compared to their purely evolutionary counterparts and to classical simulated annealing and microcanonical annealing algorithms. Experimental results on synthetic edgel maps and edgel maps derived from gray scale images are presented.     

Solving timetabling problems using a cultural algorithm

This paper addresses the solution of timetabling problems using cultural algorithms. The core idea is to extract problem domain information during the evolutionary search, and then combine it with some previously proposed operators, in order to improve performance. The proposed approach is validated using a benchmark of 20 instances, and its results are compared with respect to three other approaches: two evolutionary algorithms and simulated annealing, all of which have been previously adopted to solve timetabling problems.     

A simulated annealing method based on a specialised evolutionary algorithm

The flexible architecture of evolutionary algorithms allows specialised models to be obtained with the aim of performing as other search methods do, but more satisfactorily. In fact, there exist several evolutionary proposals in the literature that play the role of local search methods. In this paper, we make a step forward presenting a specialised evolutionary approach that carries out a search process equivalent to the one of simulated annealing. An empirical study comparing the new model with classic simulated annealing methods, hybrid algorithms and state-of-the-art optimisers concludes that the new alternative scheme for combining ideas from simulated annealing and evolutionary algorithms introduced by our proposal may outperform this kind of hybrid algorithms, and achieve competitive results with regard to proposals presented in the literature for binary-coded optimisation problems.     

Coevolutionary augmented Lagrangian methods for constrainedoptimization

This paper introduces a coevolutionary method developed for solving constrained optimization problems. This algorithm is based on the evolution of two populations with opposite objectives to solve saddle-point problems. The augmented Lagrangian approach is taken to transform a constrained optimization problem to a zero-sum game with the saddle point solution. The populations of the parameter vector and the multiplier vector approximate the zero-sum game by a static matrix game, in which the fitness of individuals is determined according to the security strategy of each population group. Selection, recombination, and mutation are done by using the evolutionary mechanism of conventional evolutionary algorithms such as evolution strategies, evolutionary programming, and genetic algorithms. Four benchmark problems are solved to demonstrate that the proposed coevolutionary method provides consistent solutions with better numerical accuracy than other evolutionary methods     

Applying genetic algorithms to game search trees

 Computer game playing is an important artificial intelligence research field in that the results can usually be applied to other related fields. One of the key computer-game-playing issues is designing effective search algorithms. Traditional search algorithms incur great temporal and spatial complexities when exploring deeply into search trees to find good next moves. Searches are thus usually not deep enough to derive good playing strategies. In this paper, we focus on one-player game search trees, and propose a genetic-algorithm-based approach to enhancing the speed and accuracy of game tree searches. Experiments show that our algorithm can improve solution accuracy and search speed.     

Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization

Randomized search heuristics like local search, tabu search, simulated annealing, or all kinds of evolutionary algorithms have many applications. However, for most problems the best worst-case expected run times are achieved by more problem-specific algorithms. This raises the question about the limits of general randomized search heuristics. Here a framework called black-box optimization is developed. The essential issue is that the problem but not the problem instance is knownto the algorithm which can collect information about the instance only by asking for the value of points in the search space. All known randomized search heuristics fit into this scenario. Lower bounds on the black-box complexity of problems are derived without complexity theoretical assumptions and are compared with upper bounds in this scenario.     

C-PSA: Constrained Pareto simulated annealing for constrained multi-objective optimization

In recent years, evolutionary algorithms (EAs) have been extensively developed and utilized to solve multi-objective optimization problems. However, some previous studies have shown that for certain problems, an approach which allows for non-greedy or uphill moves (unlike EAs), can be more beneficial. One such approach is simulated annealing (SA). SA is a proven heuristic for solving numerical optimization problems. But owing to its point-to-point nature of search, limited efforts has been made to explore its potential for solving multi-objective problems. The focus of the presented work is to develop a simulated annealing algorithm for constrained multi-objective problems. The performance of the proposed algorithm is reported on a number of difficult constrained benchmark problems. A comparison with other established multi-objective optimization algorithms, such as infeasibility driven evolutionary algorithm (IDEA), Non-dominated sorting genetic algorithm II (NSGA-II) and multi-objective Scatter search II (MOSS-II) has been included to highlight the benefits of the proposed approach.     

Systematic integration of parameterized local search into evolutionary algorithms

Application-specific, parameterized local search algorithms (PLSAs), in which optimization accuracy can be traded off with run time, arise naturally in many optimization contexts. We introduce a novel approach, called simulated heating, for systematically integrating parameterized local search into evolutionary algorithms (EAs). Using the framework of simulated heating, we investigate both static and dynamic strategies for systematically managing the tradeoff between PLSA accuracy and optimization effort. Our goal is to achieve maximum solution quality within a fixed optimization time budget. We show that the simulated heating technique better utilizes the given optimization time resources than standard hybrid methods that employ fixed parameters, and that the technique is less sensitive to these parameter settings. We apply this framework to three different optimization problems, compare our results to the standard hybrid methods, and show quantitatively that careful management of this tradeoff is necessary to achieve the full potential of an EA/PLSA combination.     

Makespan minimization for scheduling unrelated parallel machines with setup times

This study considers the problem of scheduling jobs on unrelated parallel machines with machine-dependent and job sequence-dependent setup times. In this study, a restricted simulated annealing (RSA) algorithm which incorporates a restricted search strategy is presented to minimize the makespan. The proposed RSA algorithm can effective reduce the search effort required to find the best neighborhood solution by eliminating ineffective job moves. The effectiveness and efficiency of the proposed RSA algorithm is compared with the basic simulated annealing and existing meta-heuristics on a benchmark problem dataset used in earlier studies. Computational results indicate that the proposed RSA algorithm compares well with the state-of-the-art meta-heuristic for small-sized problems, and significantly outperforms basic simulated annealing algorithm and existing algorithms for large-sized problems.     

Real-time bidirectional search: coordinated problem solving inuncertain situations

This paper investigates real-time bidirectional search (RTBS) algorithms, where two problem solvers, starting from the initial and goal states, physically move toward each other. To evaluate the RTBS performance, two kinds of algorithms are proposed and are compared to real-time unidirectional search. One is called centralized RTBS where a supervisor always selects the best action from all possible moves of the two problem solvers. The other is called decoupled RTBS where no supervisor exists and the two problem solvers independently select their next moves. Experiments on mazes and n-puzzles show that: 1) in clear situations decoupled RTBS performs better, while in uncertain situations, centralized RTBS becomes more efficient; and 2) RTBS is more efficient than real-time unidirectional search for 15-and 24-puzzles but not for randomly generated mazes. It is shown that the selection of the problem solving organization is the selection of the problem space, which determines the baseline of the organizational efficiency; once a difficult problem space is selected, the local coordination among problem solvers hardly overcome the deficit     

考虑市场因素的电力系统供需互动混合博弈强化学习算法

为对电力市场环境下电力系统供需互动问题更精确地建模,使其更好地与未来电力市场环境下需求侧负荷聚合商之间多变的关系和复杂的通信拓扑结构相匹配,本文将电力系统供需互动的Stackelberg博弈与复杂网络上反映需求侧负荷聚合商互动的演化博弈相结合,搭建考虑市场因素的电力系统供需互动混合博弈模型.并提出混合博弈强化学习算法求解相应的非凸非连续优化问题,该算法以Q学习为载体,通过引入博弈论和图论的思想,把分块协同和演化博弈的方法相结合,充分地利用博弈者之间互动博弈关系所形成的知识矩阵信息,高质量地求解考虑复杂网络上多智能体系统的非凸优化问题.基于复杂网络理论搭建的四类3机-6负荷系统和南方某一线城市电网的仿真结果表明:混合博弈强化学习算法的寻优性能比大多数集中式的智能算法好,且在不同网络下均可以保证较好的寻优结果,具有很强的适应性和稳定性.     

The impact of parametrization in memetic evolutionary algorithms

Memetic (evolutionary) algorithms integrate local search into the search process of evolutionary algorithms. As computational resources have to be spread adequately among local and evolutionary search, one has to care about when to apply local search and how much computational effort to devote to local search. Often local search is called with a fixed frequency and run for a fixed number of iterations, the local search depth. There is empirical evidence that these parameters have a significant impact on performance, but a theoretical understanding as well as concrete design guidelines are missing.     

Game model-based co-evolutionary algorithm with non-dominated memory and Euclidean distance selection mechanisms for multi-objective optimization

Many real-world problems involve simultaneous optimization of several incommensurable and often competing objectives. In the search for solutions to multi-objective optimization problems (MOPs), we find that there is no single optimum but rather a set of optimums known as the “Pareto optimal set”. Co-evolutionary algorithms are well suited to optimization problems which involve several often competing objectives. Co-evolutionary algorithms are aimed at evolving individuals through individuals competing in an objective space. In order to approximate the ideal Pareto optimal set, the search capability of diverse individuals in an objective space can be used to determine the performance of evolutionary algorithms. Non-dominated memory and Euclidean distance selection mechanisms for co-evolutionary algorithms have the goal of overcoming the limited search capability of diverse individuals in the population space. In this paper, we propose a method for maintaining population diversity in game model-based co-evolutionary algorithms, and we evaluate the effectiveness of our approach by comparing it with other methods through rigorous experiments on several MOPs.     

Coevolution versus self-play temporal difference learning for acquiring position evaluation in small-board go

Two learning methods for acquiring position evaluation for small Go boards are studied and compared. In each case the function to be learned is a position-weighted piece counter and only the learning method differs. The methods studied are temporal difference learning (TDL) using the self-play gradient-descent method and coevolutionary learning, using an evolution strategy. The two approaches are compared with the hope of gaining a greater insight into the problem of searching for "optimal" zero-sum game strategies. Using tuned standard setups for each algorithm, it was found that the temporal-difference method learned faster, and in most cases also achieved a higher level of play than coevolution, providing that the gradient descent step size was chosen suitably. The performance of the coevolution method was found to be sensitive to the design of the evolutionary algorithm in several respects. Given the right configuration, however, coevolution achieved a higher level of play than TDL. Self-play results in optimal play against a copy of itself. A self-play player will prefer moves from which it is unlikely to lose even when it occasionally makes random exploratory moves. An evolutionary player forced to perform exploratory moves in the same way can achieve superior strategies to those acquired through self-play alone. The reason for this is that the evolutionary player is exposed to more varied game-play, because it plays against a diverse population of players.     

On minimizing coding operations in network coding based multicast: an evolutionary algorithm

In telecommunications networks, to enable a valid data transmission based on network coding, any intermediate node within a given network is allowed, if necessary, to perform coding operations. The more coding operations needed, the more coding resources consumed and thus the more computational overhead and transmission delay incurred. This paper investigates an efficient evolutionary algorithm to minimize the amount of coding operations required in network coding based multicast. Based on genetic algorithms, we adapt two extensions in the proposed evolutionary algorithm, namely a new crossover operator and a neighbourhood search operator, to effectively solve the highly complex problem being concerned. The new crossover is based on logic OR operations to each pair of selected parent individuals, and the resulting offspring are more likely to become feasible. The aim of this operator is to intensify the search in regions with plenty of feasible individuals. The neighbourhood search consists of two moves which are based on greedy link removal and path reconstruction, respectively. Due to the specific problem feature, it is possible that each feasible individual corresponds to a number of, rather than a single, valid network coding based routing subgraphs. The neighbourhood search is applied to each feasible individual to find a better routing subgraph that consumes less coding resource. This operator not only improves solution quality but also accelerates the convergence. Experiments have been carried out on a number of fixed and randomly generated benchmark networks. The results demonstrate that with the two extensions, our evolutionary algorithm is effective and outperforms a number of state-of-the-art algorithms in terms of the ability of finding optimal solutions.     

Evolutionary-based heuristic generators for checkers and give-away checkers

Abstract: Two methods of genetic evolution of linear and non-linear heuristic evaluation functions for the game of checkers and give-away checkers are presented in the paper. The first method is based on the simplistic assumption that a relation 'close' to partial order can be defined over the set of evaluation functions. Hence an explicit fitness function is not necessary in this case and direct comparison between heuristics (a tournament) can be used instead. In the other approach a heuristic is developed step-by-step based on the set of training games. First, the end-game positions are considered and then the method gradually moves 'backwards' in the game tree up to the starting position and at each step the best fitted specimen from the previous step (previous game tree depth) is used as the heuristic evaluation function in the alpha-beta search for the current step. Experimental results confirm that both approaches lead to quite strong heuristics and give hope that a more sophisticated and more problem-oriented evolutionary process might ultimately provide heuristics of quality comparable to those of commercial programs.     

一种基于目标空间转换权重求和的超多目标进化算法

权重求和是基于分解的超多目标进化算法中常用的方法,相比其他方法具有计算简单、搜索效率高等优点,但难以有效处理帕累托前沿面(Pareto optimal front,PF)为非凸型的问题.为充分发挥权重求和方法的优势,同时又能处理好PF为非凸型的问题,本文提出了一种基于目标空间转换权重求和的超多目标进化算法,简称NSGA...     

New Algorithms for Solving Simple Stochastic Games

We present new algorithms for determining optimal strategies for two-player games with proba- bilistic moves and reachability winning conditions. Such games, known as simple stochastic games, were extensively studied by A.Condon [Anne Condon. The complexity of stochastic games. Information and Computation, 96(2):203–224, 1992, Anne Condon. On algorithms for simple stochastic games. In Jin-Yi Cai, editor, Advances in Computational Complexity Theory, volume 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 51–73. AMS, 1993]. Many interesting problems, including parity games and hence also mu-calculus model checking, can be reduced to simple stochastic games. It is an open problem, whether simple stochastic games can be solved in polynomial time. Our algorithms determine the optimal expected payoffs in the game. We use geometric interpre- tation of the search space as a subset of the hyper-cube [0,1]^N. The main idea is to divide this set into convex subregions in which linear optimization methods can be used. We show how one can proceed from one subregion to the other so that, eventually, a region containing the optinal payoffs will be found. The total number of subregions is exponential in the size of the game but, in practice, the algorithms need to visit only few of them to find a solution. We believe that our new algorithms could provide new insights into the difficult problem of deter- mining algorithmic complexity of simple stochastic games and other, equivallent problems.     

博弈树启发式搜索的α-β剪枝技术研究

博弈是启发式搜索的一个重要应用领域,博弈的过程可以用一棵博弈搜索树表示,通过对博弈树进行搜索求取问题的解,搜索策略常采用α-β剪枝技术。在深入研究α-β剪枝技术的基础上,提出在扩展未达到规定深度节点时,对扩展出的子节点按照估价函数大小顺序插入到搜索树中,从而在α-β剪枝过程中剪掉更多的分枝,提高搜索效率。