Alert button
Picture for D. Dumitrescu

D. Dumitrescu

Alert button

Evolving TSP heuristics using Multi Expression Programming

Add code
Bookmark button
Alert button
Sep 08, 2015
Mihai Oltean, D. Dumitrescu

Figure 1 for Evolving TSP heuristics using Multi Expression Programming
Figure 2 for Evolving TSP heuristics using Multi Expression Programming
Figure 3 for Evolving TSP heuristics using Multi Expression Programming

Multi Expression Programming (MEP) is an evolutionary technique that may be used for solving computationally difficult problems. MEP uses a linear solution representation. Each MEP individual is a string encoding complex expressions (computer programs). A MEP individual may encode multiple solutions of the current problem. In this paper MEP is used for evolving a Traveling Salesman Problem (TSP) heuristic for graphs satisfying triangle inequality. Evolved MEP heuristic is compared with Nearest Neighbor Heuristic (NN) and Minimum Spanning Tree Heuristic (MST) on some difficult problems in TSPLIB. For most of the considered problems the evolved MEP heuristic outperforms NN and MST. The obtained algorithm was tested against some problems in TSPLIB. The results emphasizes that evolved MEP heuristic is a powerful tool for solving difficult TSP instances.

* International Conference on Computational Sciences, ICCS'04, 6-9 June, Krakow, Poland, Edited by M. Bubak, G.van Albada, P. Sloot, and J. Dongarra, Vol II, pp. 670-673, Springer-Verlag, Berlin, 2004. Source code available for download at: http://www.cs.ubbcluj.ro/~moltean/evolve_heuristics.html 
Viaarxiv icon
Github IconAccess Paper or Ask Questions
Twitter IconFacebook IconLinkedin IconWhatsapp IconMessenger Icon

Distributed Pharaoh System for Network Routing

Add code
Bookmark button
Alert button
Aug 27, 2012
Camelia-M. Pintea, D. Dumitrescu

In this paper it is introduced a biobjective ant algorithm for constructing low cost routing networks. The new algorithm is called the Distributed Pharaoh System (DPS). DPS is based on AntNet algorithm. The algorithm is using Pharaoh Ant System (PAS) with an extra-exploration phase and a 'no-entry' condition in order to improve the solutions for the Low Cost Network Routing problem. Additionally it is used a cost model for overlay network construction that includes network traffic demands. The Pharaoh ants (Monomorium pharaonis) includes negative pheromones with signals concentrated at decision points where trails fork. The negative pheromones may complement positive pheromone or could help ants to escape from an unnecessarily long route to food that is being reinforced by attractive signals. Numerical experiments were made for a random 10-node network. The average node degree of the network tested was 4.0. The results are encouraging. The algorithm converges to the shortest path while converging on a low cost overlay routing network topology.

* Automat. Comput. Appl. Math. 16(1-2) (2007) 27-34  
* 4 pages, 4 figures 
Viaarxiv icon
Github IconAccess Paper or Ask Questions
Twitter IconFacebook IconLinkedin IconWhatsapp IconMessenger Icon

Sensitive Ants in Solving the Generalized Vehicle Routing Problem

Add code
Bookmark button
Alert button
Aug 27, 2012
Camelia-M. Pintea, Camelia Chira, D. Dumitrescu, Petrica C. Pop

Figure 1 for Sensitive Ants in Solving the Generalized Vehicle Routing Problem
Figure 2 for Sensitive Ants in Solving the Generalized Vehicle Routing Problem
Figure 3 for Sensitive Ants in Solving the Generalized Vehicle Routing Problem
Figure 4 for Sensitive Ants in Solving the Generalized Vehicle Routing Problem

The idea of sensitivity in ant colony systems has been exploited in hybrid ant-based models with promising results for many combinatorial optimization problems. Heterogeneity is induced in the ant population by endowing individual ants with a certain level of sensitivity to the pheromone trail. The variable pheromone sensitivity within the same population of ants can potentially intensify the search while in the same time inducing diversity for the exploration of the environment. The performance of sensitive ant models is investigated for solving the generalized vehicle routing problem. Numerical results and comparisons are discussed and analysed with a focus on emphasizing any particular aspects and potential benefits related to hybrid ant-based models.

* INT J COMPUT COMMUN, VI(4) (2011) 731-738  
* 5 pages 
Viaarxiv icon
Github IconAccess Paper or Ask Questions
Twitter IconFacebook IconLinkedin IconWhatsapp IconMessenger Icon

New results of ant algorithms for the Linear Ordering Problem

Add code
Bookmark button
Alert button
Aug 27, 2012
Camelia-M. Pintea, Camelia Chira, D. Dumitrescu

Figure 1 for New results of ant algorithms for the Linear Ordering Problem
Figure 2 for New results of ant algorithms for the Linear Ordering Problem
Figure 3 for New results of ant algorithms for the Linear Ordering Problem
Figure 4 for New results of ant algorithms for the Linear Ordering Problem

Ant-based algorithms are successful tools for solving complex problems. One of these problems is the Linear Ordering Problem (LOP). The paper shows new results on some LOP instances, using Ant Colony System (ACS) and the Step-Back Sensitive Ant Model (SB-SAM).

* An. Univ. Vest Timis., Ser. Mat.-Inform. 48, No. 3, 139-150 (2010)  
* 5 pages, 5 figures Zbl:06048718 
Viaarxiv icon
Github IconAccess Paper or Ask Questions
Twitter IconFacebook IconLinkedin IconWhatsapp IconMessenger Icon