• Articles • Previous Articles     Next Articles

Orthogonal Methods Based Ant Colony Search for Solving Continuous Optimization Problems

Xiao-Min Hu{1,2, Jun Zhang{1,2, and Yun Li3   

  1. 1Department of Computer Science, Sun Yat-Sen University, Guangzhou 510275, China 2Key Laboratory of Digital Life (Sun Yat-Sen University), Ministry of Education, Guangzhou 510275, China 3Department of Electronics and Electrical Engineering, University of Glasgow, Glasgow G12 8LT, Scotland, U.K.
  • Revised:2007-11-06 Online:2008-01-15 Published:2008-01-10

Research into ant colony algorithms for solving continuous optimization problems forms one of the most significant and promising areas in swarm computation. Although traditional ant algorithms are designed for combinatorial optimization, they have shown great potential in solving a wide range of optimization problems, including continuous optimization. Aimed at solving continuous problems effectively, this paper develops a novel ant algorithm termed ``continuous orthogonal ant colony'' (COAC), whose pheromone deposit mechanisms would enable ants to search for solutions collaboratively and effectively. By using the orthogonal design method, ants in the feasible domain can explore their chosen regions rapidly and efficiently. By implementing an ``adaptive regional radius'' method, the proposed algorithm can reduce the probability of being trapped in local optima and therefore enhance the global search capability and accuracy. An elitist strategy is also employed to reserve the most valuable points. The performance of the COAC is compared with two other ant algorithms for continuous optimization --- API and CACO by testing seventeen functions in the continuous domain. The results demonstrate that the proposed COAC algorithm outperforms the others.

Key words: self-similar traffic; performance analysis; simulation;



[1] Deneubourg J L, Aron S, Goss S, Pasteels J M. The self-organizing exploratory pattern of the Argentine ant. -\it Journal of Insect Behavior}, 1990, 3: 159--168.

[2] Goss S, Aron S, Deneubourg J L, Pasteels J M. Self-organized shortcuts in the Argentine ant. -\it Naturwissenschaften}, 1989, 76(12): 579--581.

[3] Dorigo M, St\"utzle T. -Ant Colony Optimization}. the MIT Press, 2003.

[4] Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem. -\it IEEE. Trans. Evol. Comput.}, 1997, 1(1): 53--66.

[5] Toth P, Vigo D. -The Vehicle Routing Problem}. -SIAM Monographs on Discrete Mathematics and Applications}, Philadelphia, Society for Industrial \& Applied Mathematics, 2001.

[6] Gambardella L M, Taillard \'E D, Agazzi G. MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows. -New Ideas in Optimization}, Corne D, Dorigo M, Glover F (eds.), London, McGraw Hill, 1999, pp.63--76.

[7] Zhang J, Hu X M, Tan X, Zhong J H, Huang Q. Implementation of an ant colony optimization technique for job shop scheduling problem. -\it Transactions of the Institute of Measurement and Control}, 2006, 28(1): 1--16.

[8] Zecchin A C, Simpson A R, Maier H R, Nixon J B. Parametric study for an ant algorithm applied to water distribution system optimization. -\it IEEE Trans. Evol. Comput.}, 2005, 9: 175--191.

[9] Parpinelli R S, Lopes H S, Freitas A A. Data mining with an ant colony optimization algorithm. -\it IEEE Trans. Evol. Comput.}, 2002, 4: 321--332.

[10] Sim K M, Sun W H. Ant colony optimization for routing and load-balancing: Survey and new directions. -\it IEEE Trans. Systems, Man, and Cybernetics --Part A: System and Humans}, 2003, 33: 560--572.

[11] Bilchev G, Parmee I C. The ant colony metaphor for searching continuous design spaces. In -\it Proc. the AISB Workshop on Evolutionary Computation}, University of Sheffield, UK, -\it LNCS} 933, Springer-Verlag, Berlin, Germany, 1995, pp.25--39.

[12] Wodrich M, Bilchev G. Cooperative distributed search: The ant's way. -\it Control and Cybernetics}, 1997, 3: 413--446.

[13] Mathur M, Karale S B, Priye S, Jyaraman V K, Kulkarni B D. Ant colony approach to continuous function optimization. -\it Ind. Eng. Chem. Res}., 2000, 39: 3814--3822.

[14] Holland J H. Adaptation in Natural and Artificial Systems. Second Edition (First Edition, 1975), Cambridge: the MIT Press, MA, 1992.

[15] Monmarch\'e N, Venturini G, Slimane M. On how -\it Pachycondyla apicalis} ants suggest a new search algorithm. -\it Future Generation Computer Systems}, 2000, 16: 937--946.

[16] Dr\'eo J, Siarry P. Continuous interacting ant colony algorithm based on dense heterarchy. -\it Future Generation Computer Systems}, 2004, 20: 841--856.

[17] Dr\'eo J, Siarry P. A new ant colony algorithm using the heterarchical concept aimed at optimization of multiminima continuous functions. In -\it Proc. ANTS} 2002, Brussels, Belgium, -\it LNCS} 2463, 2002, pp.216--221.

[18] Socha K. ACO for continuous and mixed-variable optimization. In -\it Proc. ANTS} 2004, Brussels, Belgium, -\it LNCS} 3172, 2004, pp.25--36.

[19] Socha K, Dorigo M. Ant colony optimization for continuous domains. -\it Eur. J. Oper. Res.}, 2008, 185(3): 1155--1173.

[20] Pourtakdoust S H, Nobahari H. An extension of ant colony system to continuous optimization problems. In -\it Proc. ANTS} 2004, Brussels, Belgium, -\it LNCS} 3172, 2004, pp.294--301.

[21] Kong M, Tian P. A binary ant colony optimization for the unconstrained function optimization problem. In -\it Proc. International Conference on Computational Intelligence and Security $($CIS'05$)$}, Xi'an, China, -\it LNAI} 3801, 2005, pp.682--687.

[22] Kong M, Tian P. A direct application of ant colony optimization to function optimization problem in continuous domain. In -\it Proc. ANTS} 2006, Brussels, Belgium, -\it LNCS} 4150, 2006, pp.324--331.

[23] Chen L, Shen J, Qin L, Chen H J. An improved ant colony algorithm in continuous optimization. -\it Journal of Systems Science and Systems Engineering}, 2006, 12(2): 224--235.

[24] Dr\'eo J, Siarry P. An ant colony algorithm aimed at dynamic continuous optimization. -\it Appl. Math. Comput.}, 2006, 181: 457--467.

[25] Chen L, Sheng J, Qin L, Chen H J. An improved ant colony algorithm in continuous optimization. -\it Journal of Systems Science and Systems Engineering}, 2003, 12(2): 224--235.

[26] Feng Y J, Feng Z R. An immunity-based ant system for continuous space multi-modal function optimization. In -\it Proc. the Third International Conference on Machine Learning and Cybernetics}, Shanghai, August 26--29, 2004, pp.1050--1054.

[27] Shelokar P S, Siarry P, Jayaraman V K, Kulkarni B D. Particle swarm and ant colony algorithms hybridized for improved continuous optimization. -\it Appl. Math. Comput.}, 2006, doi: 10.1016/j.amc. 2006.09.098.

[28] Rao C R. Factorial experiments derivable from combinatorial arrangements of arrays. -\it J. Royal Statist. Soc.}, 1947, 9(Suppl.): 128--139.

[29] Bush K A. Orthogonal arrays
[Dissertation]. University of North Carolina, Chapel Hill, 1950.

[30] Math Stat Res Group, Chinese Acad Sci. -Orthogonal Design}. Bejing: People Education Pub., 1975. (in Chinese)

[31] Fang K T, Wang Y. -Number-Theoretic Methods in Statistics}. New York: Chapman \& Hall, 1994.

[32] Hedayat A S, Sloane N J A, Stufken J. -Orthogonal Arrays: Theory and Applications}. New York: Springer-Verlag, 1999.

[33] Nathanson M B. -Elementary Methods in Number Theory.} New York: Springer-Verlag, 2000.

[34] Zhang Q, Leung Y W. An orthogonal genetic algorithm for multimedia multicast routing. -\it IEEE Trans. Evolutionary Computation}, 1999, 3(1): 53--62.

[35] Leung Y W, Wang W. An orthogonal genetic algorithm with quantization for global numerical optimization. -\it IEEE Trans. Evol. Comput.}, 2001, 5(1): 41--53.

[36] Ho S Y, Chen J H. A genetic-based systematic reasoning approach for solving traveling salesman problems using an orthogonal array crossover. In -\it Proc. the Fourth Internal Conference/Exhibition on High Performance Computing in the Asia-Pacific Region}, May 2000, 2: 659--663.

[37] Liang X B. Orthogonal designs with maximal rates. -\it IEEE Trans. Information Theory}, 2003, 49(10): 2468--2503.

[38] Tanaka H. Simple genetic algorithm started by orthogonal design of experiments. In -\it Proc. SICE Annual Conference in Sapporp}, August 2004, pp.1075--1078.

[39] Salomon R. Reevaluating genetic algorithm performance under coordinate rotation of benchmark functions. -\it BioSystems}, 1996, 39: 263--278.
[1] Hua Wang, Xiao-Yu He, Liu-Yang Chen, Jun-Ru Yin, Li Han, Hui Liang, Fu-Bao Zhu, Rui-Jie Zhu, Zhi-Min Gao, Ming-Liang Xu. Cognition-Driven Traffic Simulation for Unstructured Road Networks [J]. Journal of Computer Science and Technology, 2020, 35(4): 875-888.
[2] Sven Pullwitt, Robert Hartung, Ulf Kulau, Lars Wolf. Towards Accurate Bit Error Simulation in Wireless Sensor Networks Including Environmental Influences [J]. Journal of Computer Science and Technology, 2020, 35(4): 809-824.
[3] Bo Ren, Xu-Yun Yang, Ming C. Lin, Nils Thuerey, Matthias Teschner, Chenfeng Li. Visual Simulation of Multiple Fluids in Computer Graphics: A State-of-the-Art Report [J]. , 2018, 33(3): 431-451.
[4] Feng-Yu Li, Chang-Bo Wang, Hong Qin, Hong-Yan Quan. Augmented Flow Simulation based on Tight Coupling between Video Reconstruction and Eulerian Models [J]. , 2018, 33(3): 452-462.
[5] Xiao-Kun Wang, Xiao-Juan Ban, Ya-Lan Zhang, Si-Nuo Liu, Peng-Fei Ye. Surface Tension Model Based on Implicit Incompressible Smoothed Particle Hydrodynamics for Fluid Simulation [J]. , 2017, 32(6): 1186-1197.
[6] Shi-Yu Jia, Zhen-Kuan Pan, Guo-Dong Wang, Wei-Zhong Zhang, CCF Xiao-Kang Yu. Stable Real-Time Surgical Cutting Simulation of Deformable Objects Embedded with Arbitrary Triangular Meshes [J]. , 2017, 32(6): 1198-1213.
[7] Shihong Xia, Lin Gao, Yu-Kun Lai, Ming-Ze Yuan, Jinxiang Chai. A Survey on Human Performance Capture and Animation [J]. , 2017, 32(3): 536-554.
[8] Li-Li Xu, Hui-Min Lin. Complete Proof Systems for Amortised Probabilistic Bisimulations [J]. , 2016, 31(2): 300-316.
[9] Erika Rosas, Nicolás Hidalgo, Veronica Gil-Costa, Carolina Bonacic, et al. Survey on Simulation for Mobile Ad-Hoc Communication for Disaster Scenarios [J]. , 2016, 31(2): 326-349.
[10] Yu Ji, You-Hui Zhang, Wei-Min Zheng. Modelling Spiking Neural Network from the Architecture Evaluation Perspective [J]. , 2016, 31(1): 50-59.
[11] Fa-Ming Li, Xiao-Wu Chen, Bin Zhou, Fei-Xiang, Lu Kan Guo, Qiang Fu. Monocular Video Guided Garment Simulation [J]. , 2015, 30(3): 528-539.
[12] Ming-Liang Xu, Hao Jiang, Xiao-Gang Jin, Zhigang Deng. Crowd Simulation and Its Applications: Recent Advances [J]. , 2014, 29(5): 799-811.
[13] Yan-Fang Ma and Min Zhang. The Infinite Evolution Mechanism of ε-Bisimilarity [J]. , 2013, 28(6): 1097-1105.
[14] Youngjun Kim, Dongjune Chang, Jungsik Kim, and Sehyung Park. Gallbladder Removal Simulation for Laparoscopic Surgery Training: A Hybrid Modeling Method [J]. , 2013, 28(3): 499-507.
[15] Wei-Neng Chen, Member IEEE, and Jun Zhang, Senior Member, IEEE. Scheduling Multi-Mode Projects under Uncertainty to Optimize Cash Flows: A Monte Carlo Ant Colony System Approach [J]. , 2012, 27(5): 950-965.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved