文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Ant algorithms Review and future applications
侵权投诉

Ant algorithms Review and future applications

A search for a robust optimization methodology for addressing dynamic problems in business and engineering has been in research for the past decade. One such tool in the array of algorithms is the Ant algorithms, inspired by the behavior of the real ants.

3. Applications

Industry environment has many optimization applications that span from task allocation jobs like factory scheduling to complex business decision-making process. According to the computer world report [9], real ants exhibit great level of centralized and dynamic behavior of reorienting its path around an obstacle, which is a result of a collective decision making process. This report states that, this behavior is similar to, “General Motors Corporation's Saturn subsidiary which uses distributed systems to control the flow of part assemblies. Instead of having each factory machine's actions preprogrammed and unvarying, Saturn's machines can sense the type and state of a part and adapt their actions on the fly ” [9]. This indicates that the new artificial ant agents can be successfully programmed for dynamic environments.

There are many different heuristics named based on the general ant algorithms structure. Dorigo, Maniezzo and Colorni [7, 10] proposed the first class of ant algorithms called the ant system and introduced three types of ant algorithms called the ant-density, the ant quantity, and the ant cycle. The typical problem, which was researched, was the well-known Traveling Salesman Problem (TSP). With the initial success on this there has been an active research contribution towards applying the ant algorithms to the various problem domains. The application of ant algorithms with the related heuristic name as applied to the quadratic assignment problem, traveling salesman problem, vehicle routing problem, connection-oriented network routing, sequential ordering, graph coloring, shortest common sequence problem, frequency assignment problem, multiple knapsack problem, optical network problem, single machine total tardiness problem are dealt extensively by Dorigo and Di Caro [6,11] and Dorigo and Stutzle

[12, 13]. In an effort to identify the real time application other than the conventional combinatorial problems, consolidated information about ant algorithms to various practical scenarios are provided in this paper.

According to Cartwright and Hopkins [14] evolutionary algorithms have curtail applications in the development and synthesis of chemicals. The authors provide comparative analysis of algorithms used for the purpose and detail the application of ant system to the chemical synthesis problem. A ten-step reaction was used as an example to compare the results. To highlight the complexity of the problem, imagine that there are 810 (1,073,741,824) possible routes for the chemical reactions right from the initial starting substance to the final synthesized chemical. For this problem the ant system algorithm produced a maximum yield of 70%, which is 30% more than result of the genetic algorithm. This clearly indicates the goodness of ant algorithms and its practical application.

Many applications for the job shop scheduling problems can be found in the literature. Maniezzo and Carbonaro

[15] reviewed the various ant algorithms under the framework of Ant Colony Optimization (ACO) algorithm. They also provide a comparative results obtained by the applications of ACO algorithm to many combinatorial optimization problems including job shop scheduling and vehicle routing.

Zwaan and Marques [16] proposed an ant system for the job shop scheduling with reference to the Muth-Thompson 6/6/G/Cmax job shop problem. Ten jobs 10 machines and 20 jobs 10 machines problems were studied for a range of Cmax and the effects of parameters, which govern the ant algorithms, and fine tuning of them was reported. For a known value of Cmax the optimal solution obtained from ant system was reported to vary from 8 to 14% in case of 10 jobs problem and 26 to 31.9% in case of 20 jobs problem. This elucidates that the optimization of the parameters of the ant algorithms greatly influences the problem it can solve.

Cicirello and Smith [17] introduced the application of AC2 ant algorithms for decentralized decision-making policies in the shop floor. Typical scenarios considered were the two machines one job, two assembly lines one job, two machines two job and four machines two job types. AC2 algorithm is compared with two other heuristics such as the random selection heuristic and earliest completion time heuristic. In all the cases for a simulation time frame of 1000 units and 2000-5000 units the AC2 algorithm was found to give better solution than the other two heuristics.

Gravel et al. [18] applied ant algorithms to the scheduling of jobs in a foundry environment. The algorithm type used was the ACO algorithm with look-ahead features by which the authors obtained better solution than the ACO algorithm without look-ahead features. This elucidates the practical applicability of ant algorithms to common problems faced in the manufacturing industry.

Balad [19] elucidated the application of ant colony optimisation (ACO) algorithm with tabu search for designing a transmission tower. The objective was to design for the minimum tower weight. This application illustrates a discrete-variable optimal structural design process, which has to over come the local minima. It also states that the lowest weight obtained by using ACO method is superior to many other latest heuristics.

Artificial ants are also used for creating on-line digital arts with the colour deposition tool called the ‘ANTBRUSH’

[20]. The ant brush is inspired by the food collection process of the real ants, which is done by the transfer of small chunks of food samples from source to home. The colour selection process by the experienced painter involves picking of colours of different intensity based on their previously used sets of colours. Ant algorithms govern the colour selection process resulting in an efficient set of colours that can be cached in the memory for future reference.

上一页第4页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email