Coordination of intelligent agents in real-time search

Search is a fundamental problem-solving method in artificial intelligence. Traditional off-line search algorithms attempt to find an optimal solution whereas real-time search algorithms try to find a suboptimal solution more quickly than traditional algorithms to meet real-time constraints. In this work, a new multi-agent real-time search algorithm is developed and its effectiveness is illustrated on a sample domain, namely maze problems. Searching agents can see their environment with a specified visual depth and hence can partially observe their environment. An agent makes use of its partial observation to select a next move, instead of using only one-move-ahead information. Furthermore agents cooperate through a marking mechanism to be able to search different parts of the search space. When an agent selects its next move, it marks its direction of move before executing the move. When another agent comes to this position, it sees this mark and, if possible, moves in a different direction than the previously selected direction. In this way, marking helps agents coordinate their moves with other agents. Although coordination brings an overhead, from experiments we observe that this mechanism is effective in both search time and solution length in maze problems.     

Elicitation strategies for soft constraint problems with missing preferences: Properties,algorithms and experimental studies

We consider soft constraint problems where some of the preferences may be unspecified. This models, for example, settings where agents are distributed and have privacy issues, or where there is an ongoing preference elicitation process. In this context, we study how to find an optimal solution without having to wait for all the preferences. In particular, we define algorithms, that interleave search and preference elicitation, to find a solution which is necessarily optimal, that is, optimal no matter what the missing data will be, with the aim to ask the user to reveal as few preferences as possible. We define a combined solving and preference elicitation scheme with a large number of different instantiations, each corresponding to a concrete algorithm, which we compare experimentally. We compute both the number of elicited preferences and the user effort, which may be larger, as it contains all the preference values the user has to compute to be able to respond to the elicitation requests. While the number of elicited preferences is important when the concern is to communicate as little information as possible, the user effort measures also the hidden work the user has to do to be able to communicate the elicited preferences. Our experimental results on classical, fuzzy, weighted and temporal incomplete CSPs show that some of our algorithms are very good at finding a necessarily optimal solution while asking the user for only a very small fraction of the missing preferences. The user effort is also very small for the best algorithms.     

A stochastic algorithm for makespan minimized multi-agent path planning in discrete space

Makespan minimized multi-agent path planning (MAPP) requires the minimization of the time taken by the slowest agents to reach its destination. The resulting minimax objective function is non-smooth and the search for an optimal solution in MAPP can be intractable. In this work, a maximum entropy function is adopted to approximate the minimax objective function. An iterative algorithm named probabilistic iterative makespan minimization (PIMM) is then proposed to approximate a makespan minimized MAPP solution by solving a sequence of computationally hard MAPP minimization problems with a linear objective function. At each iteration, a novel local search algorithm called probabilistic iterative path coordination (PIPC) is used to find a sufficiently good solution for each MAPP minimization problem. Experimental results from comparative studies with existing MAPP algorithms show that the proposed algorithm strikes a good tradeoff between the quality of the makespan minimized solution and the computational cost incurred.     

Local Search-based Hybrid Algorithms for Finding Golomb Rulers

The Golomb ruler problem is a very hard combinatorial optimization problem that has been tackled with many different approaches, such as constraint programming (CP), local search (LS), and evolutionary algorithms (EAs), among other techniques. This paper describes several local search-based hybrid algorithms to find optimal or near-optimal Golomb rulers. These algorithms are based on both stochastic methods and systematic techniques. More specifically, the algorithms combine ideas from greedy randomized adaptive search procedures (GRASP), scatter search (SS), tabu search (TS), clustering techniques, and constraint programming (CP). Each new algorithm is, in essence, born from the conclusions extracted after the observation of the previous one. With these algorithms we are capable of solving large rulers with a reasonable efficiency. In particular, we can now find optimal Golomb rulers for up to 16 marks. In addition, the paper also provides an empirical study of the fitness landscape of the problem with the aim of shedding some light about the question of what makes the Golomb ruler problem hard for certain classes of algorithm.     

A new effective operator for the hybrid algorithm for solving global optimisation problems

Hybrid algorithms have been recently used to solve complex single-objective optimisation problems. The ultimate goal is to find an optimised global solution by using these algorithms. Based on the existing algorithms (HP_CRO, PSO, RCCRO), this study proposes a new hybrid algorithm called MPC (Mean-PSO-CRO), which utilises a new Mean-Search Operator. By employing this new operator, the proposed algorithm improves the search ability on areas of the solution space that the other operators of previous algorithms do not explore. Specifically, the Mean-Search Operator helps find the better solutions in comparison with other algorithms. Moreover, the authors have proposed two parameters for balancing local and global search and between various types of local search, as well. In addition, three versions of this operator, which use different constraints, are introduced. The experimental results on 23 benchmark functions, which are used in previous works, show that our framework can find better optimal or close-to-optimal solutions with faster convergence speed for most of the benchmark functions, especially the high-dimensional functions. Thus, the proposed algorithm is more effective in solving single-objective optimisation problems than the other existing algorithms.     

多因素制约的迷宫问题最优解的求解算法

介绍迷宫问题及其最优解,引入多因素制约的迷宫问题。重点讨论多因素制约迷宫问题最优解的含义及基于广度优先搜索的求解算法,并通过两个实例分析如何基于广度优先搜索算法求解这类迷宫问题的最优解,并给出算法的伪代码。最后,进一步讨论和总结这类迷宫问题最优解的求解算法。     

Problem difficulty for tabu search in job-shop scheduling

Tabu search algorithms are among the most effective approaches for solving the job-shop scheduling problem (JSP). Yet, we have little understanding of why these algorithms work so well, and under what conditions. We develop a model of problem difficulty for tabu search in the JSP, borrowing from similar models developed for SAT and other NP-complete problems. We show that the mean distance between random local optima and the nearest optimal solution is highly correlated with the cost of locating optimal solutions to typical, random JSPs. Additionally, this model accounts for the cost of locating sub-optimal solutions, and provides an explanation for differences in the relative difficulty of square versus rectangular JSPs. We also identify two important limitations of our model. First, model accuracy is inversely correlated with problem difficulty, and is exceptionally poor for rare, very high-cost problem instances. Second, the model is significantly less accurate for structured, non-random JSPs. Our results are also likely to be useful in future research on difficulty models of local search in SAT, as local search cost in both SAT and the JSP is largely dictated by the same search space features. Similarly, our research represents the first attempt to quantitatively model the cost of tabu search for any NP-complete problem, and may possibly be leveraged in an effort to understand tabu search in problems other than job-shop scheduling.     

An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. Although the traditional optimization algorithms could obtain preferable results in solving the mono-objective FJSP. However, they are very difficult to solve multi-objective FJSP very well. In this paper, a particle swarm optimization (PSO) algorithm and a tabu search (TS) algorithm are combined to solve the multi-objective FJSP with several conflicting and incommensurable objectives. PSO which integrates local search and global search scheme possesses high search efficiency. And, TS is a meta-heuristic which is designed for finding a near optimal solution of combinatorial optimization problems. Through reasonably hybridizing the two optimization algorithms, an effective hybrid approach for the multi-objective FJSP has been proposed. The computational results have proved that the proposed hybrid algorithm is an efficient and effective approach to solve the multi-objective FJSP, especially for the problems on a large scale.     

图着色问题的一个最小冲突权值学习算法

图着色问题(GCP)是NP完全问题．近年来求解GCP的启发式局部搜索算法引起人们的关注,GSAT是最著名的局部搜索算法之一．许多局部搜索算法引入跳出局部极小的机制来提高搜索效率,权值学习是一种被广泛采用的方式之一．我们从一些权值学习局部搜索算法抽象出一个通用的权值学习算法(SWLA),进一步把SWLA和GSAT相结合提出了最小冲突权值学习算法(MCWLA),算法还应用还原策略和“权值交叉”算子来提高搜索后期的效率．算法在求解一些难解测试范例时显示出较高的效率,能求得GSAT及SWLA无法求得的最优解．     

一种动态划分的混合连续域蚁群优化算法

连续域蚁群优化算法在处理高维问题时易陷入局部最优,而且收敛速度较慢。针对这些问题,提出了一种改进的连续域蚁群优化算法。该算法将解划分为优解和劣解两部分,并在迭代过程中动态调整优解和劣解的数目。对于优解,利用全局搜索策略进行预处理,这样能提高算法的收敛速度和收敛精度。对于劣解,则利用随机搜索策略进行预处理,这样能扩大搜索范围,增强搜索能力。通过标准测试函数对所提算法进行测试,结果表明改进策略能够有效提高连续域蚁群优化算法的收敛速度并改善解的质量。     

Software prototype for solving multi-objective machining optimization problems: Application in non-conventional machining processes

For an effective and efficient application of machining processes it is often necessary to consider more than one machining performance characteristics for the selection of optimal machining parameters. This implies the need to formulate and solve multi-objective optimization problems. In recent years, there has been an increasing trend of using meta-heuristic algorithms for solving multi-objective machining optimization problems. Although having the ability to efficiently handle highly non-linear, multi-dimensional and multi-modal optimization problems, meta-heuristic algorithms are plagued by numerous limitations as a consequence of their stochastic nature. To overcome some of these limitations in the machining optimization domain, a software prototype for solving multi-objective machining optimization problems was developed. The core of the developed software prototype is an algorithm based on exhaustive iterative search which guarantees the optimality of a determined solution in a given discrete search space. This approach is justified by a continual increase in computing power and memory size in recent years. To analyze the developed software prototype applicability and performance, four case studies dealing with multi-objective optimization problems of non-conventional machining processes were considered. Case studies are selected to cover different formulations of multi-objective optimization problems: optimization of one objective function while all the other are converted into constraints, optimization of a utility function which combines all objective functions and determination of a set of Pareto optimal solutions. In each case study optimization solutions that had been determined by past researchers using meta-heuristic algorithms were improved by using the developed software prototype.     

Local Search Algorithms for the Maximal Planar Layout Problem

The problem of laying out facilities is practically important in a modern manufacturing environment. This problem can be formulated as a weighted maximal planar graph in which vertices represent facilities and edge weights represent desirability measures between facilities. The objective is to find a planar graph that can be drawn on a plane without any edges intersecting with the highest sum of edge weights. Exact solution method can only solve small sized problems. In this paper, local search algorithms based on steepest ascent, hybrid simulated annealing and tabu search with a non-monotonic cooling schedule, and tabu search with a hashing function are developed to obtain near-optimal solutions. Different search strategies are investigated. All the developed algorithms are compared with existing construction methods and a branch and bound exact algorithm on a set of practical size problems. The proposed algorithms performed very well in terms of solution quality and computation time.     

Methods of search for stable solutions of some optimization problems in the theory of recognition by precedents

In constructing some models of recognition algorithms, there arise a number of optimization problems. The search for the optimal consistent subsystem of a given system of linear inequalities plays an important role in the process of data analysis in the theory of recognition by precedent. The optimality of a required subsystem is defined by a number of the conditions imposed on it. Earlier the author developed several algorithms for solving the problems of this type. These algorithms are based on exhaustive search for nodal subsystems of a given system of linear inequalities. In the search for optimal consistent subsystem, these algorithms find boundary decisions. However, in practical application often it is necessary to find a stable solution. So, when looking for logical regularities of a special type, it is required to find a set of non-degenerate polyhedra describing a certain class of objects in a space of features. Therefore, linear inequalities systems corresponding to these polyhedra must be stable. In this paper, we propose a method for modifying the previously developed algorithms to select the stable consistent subsystem of highest possible power and find its stable solution.     

Variable neighborhood search for the Vertex Separation Problem

The Vertex Separation Problem belongs to a family of optimization problems in which the objective is to find the best separator of vertices or edges in a generic graph. This optimization problem is strongly related to other well-known graph problems; such as the Path-Width, the Node Search Number or the Interval Thickness, among others. All of these optimization problems are NP-hard and have practical applications in VLSI (Very Large Scale Integration), computer language compiler design or graph drawing. Up to know, they have been generally tackled with exact approaches, presenting polynomial-time algorithms to obtain the optimal solution for specific types of graphs. However, in spite of their practical applications, these problems have been ignored from a heuristic perspective, as far as we know. In this paper we propose a pure 0-1 optimization model and a metaheuristic algorithm based on the variable neighborhood search methodology for the Vertex Separation Problem on general graphs. Computational results show that small instances can be optimally solved with this optimization model and the proposed metaheuristic is able to find high-quality solutions with a moderate computing time for large-scale instances.     

On multiprocessor task scheduling using efficient state space search approaches

Obtaining an optimal schedule for a set of precedence-constrained tasks is a well-known NP-complete problem in its general form. In view of the intractability of the problem, most of the previous work relies on heuristics that try to find reasonably high quality solutions in an acceptable amount of time. While optimal polynomial-time algorithms are known only for a few simple cases (and in other cases can only be obtained through an exhaustive search with prohibitively high time complexity), they may be critically important for applications in which performance is the prime objective. Optimal solutions can also serve as a reference to test the performance of various heuristics. Moreover, an optimal schedule for a program at hand needs to be determined only once (and off-line) but the program using that schedule is in general executed several times. In this paper, we propose optimal algorithms for static scheduling of task graphs with arbitrary parameters to multiple homogeneous processors. The first algorithm is based on the A^* search technique and uses a computationally efficient cost function for guiding the search with reduced complexity. Additionally, we propose a number of effective state-pruning techniques to reduce the search space. For further lowering the complexity, we propose an efficient parallelization of the search algorithm. We parallelize the algorithm with reduced interprocessor communication as well as with static and dynamic load-balancing schemes to evenly distribute the search states to the processors. We also propose an approximate algorithm that guarantees a bounded deviation from the optimal solution but executes in a considerably shorter time. Based on an extensive experimental evaluation of the algorithms, we conclude that the parallel algorithm with pruning techniques is an efficient scheme for generating optimal solutions of reasonably large problems while the approximate algorithm is effective if slightly degraded solutions are acceptable.     

Software prototype for validation of machining optimization solutions obtained with meta-heuristic algorithms

Optimization of machining processes is of primary importance for increasing machining efficiency and economics. Determining optimal values of machining parameters is performed by applying optimization algorithms to mathematical models of relationships between machining parameters and machining performance measures. In recent years, there has been an increasing trend of using empirical models and meta-heuristic optimization algorithms. The use of meta-heuristic optimization algorithms is justified because of their ability to handle highly non-linear, multi-dimensional and multi-modal optimization problems. Meta-heuristic algorithms are powerful optimization tools which provide high quality solutions in a short amount of computational time. However, their stochastic nature creates the need to validate the obtained solutions. This paper presents a software prototype for single and multi-objective machining process optimization. Since it is based on an exhaustive iterative search, it guarantees the optimality of determined solution in given discrete search space. The motivation for the development of the presented software prototype was the validation of machining optimization solutions obtained by meta-heuristic algorithms. To analyze the software prototype applicability and performance, six case studies of machining optimization problems, both single and multi-objective, were considered. In each case study the optimization solutions that had been determined by past researchers using meta-heuristic algorithms were either validated or improved by using the developed software prototype.     

求解0-1背包问题的混合贪婪遗传算法

求解0-1背包问题（KP）的最优解的时候,传统遗传算法（GA）的局部求精能力不足而简单局部搜索算法的全局探索能力有限,针对上述问题,将这两个算法整合并提出了混合贪婪遗传算法（HGGA）。在GA全局搜索框架下增加局部搜索模块,并改进传统仅基于物品价值密度的修复算子,增加基于物品价值的贪婪混合选项,从而加速寻优过程。HGGA一方面引导种群在进化的优质解空间中展开精细搜索,另一方面依靠GA的经典操作算子开拓全局搜索空间,从而达到算法求精能力和开拓能力的良好平衡。HGGA分别在三组数据上做了测试,结果表明在第一组15个测试用例中的12个上,HGGA能够百分百找到最优解,成功率达到80%;在第二组小规模数据集上,HGGA的性能明显好于其他同类GA和其他元启发算法;在第三组大规模数据集上,HGGA较其他元启发式算法具有更好的稳定性和高效性。     

A machine-order search space for job-shop scheduling problems

This paper proposes a methodology for real‐time job‐shop scheduling problems. It introduces a new classification of the scheduling methods for JSSPs with emphasis on the search methods and the significance of the search space. Subsequently, a machine‐order search space is proposed as a new framework in which different single‐machine scheduling algorithms and search methods can be incorporated to solve JSSPs. An optimization model relating makespan minimization and the proposed machine‐order search space is also described. The proposed methodology finds an optimal solution by searching a proper machine order in the machine‐order search space and scheduling the machines one by one in this order. Such an approach significantly reduces the size of the search space, and hence the computing efforts. As a result, scheduling of large JSSPs in real‐time becomes practicable.     

A learning automata-based algorithm for determination of the number of hidden units for three-layer neural networks

There is no method to determine the optimal topology for multi-layer neural networks for a given problem. Usually the designer selects a topology for the network and then trains it. Since determination of the optimal topology of neural networks belongs to class of NP-hard problems, most of the existing algorithms for determination of the topology are approximate. These algorithms could be classified into four main groups: pruning algorithms, constructive algorithms, hybrid algorithms and evolutionary algorithms. These algorithms can produce near optimal solutions. Most of these algorithms use hill-climbing method and may be stuck at local minima. In this article, we first introduce a learning automaton and study its behaviour and then present an algorithm based on the proposed learning automaton, called survival algorithm, for determination of the number of hidden units of three layers neural networks. The survival algorithm uses learning automata as a global search method to increase the probability of obtaining the optimal topology. The algorithm considers the problem of optimization of the topology of neural networks as object partitioning rather than searching or parameter optimization as in existing algorithms. In survival algorithm, the training begins with a large network, and then by adding and deleting hidden units, a near optimal topology will be obtained. The algorithm has been tested on a number of problems and shown through simulations that networks generated are near optimal.     

Large neighbourhood search algorithms for the founder sequence reconstruction problem

The reconstruction of founder genetic sequences of a population is a relevant issue in evolutionary biology research. The problem consists in finding a biologically plausible set of genetic sequences (founders), which can be recombined to obtain the genetic sequences of the individuals of a given population. The reconstruction of these sequences can be modelled as a combinatorial optimisation problem in which one has to find a set of genetic sequences such that the individuals of the population under study can be obtained by recombining founder sequences minimising the number of recombinations. This problem is called the founder sequence reconstruction problem. Solving this problem can contribute to research in understanding the origins of specific genotypic traits. In this paper, we present large neighbourhood search algorithms to tackle this problem. The proposed algorithms combine a stochastic local search with a branch-and-bound algorithm devoted to neighbourhood exploration. The developed algorithms are thoroughly evaluated on three different benchmark sets and they establish the new state of the art for realistic problem instances.