Sizing analog, mixed-signal, and particularly radio-frequency circuits generally relies on the experience of the designer. Metaheuristics have been recently proposed, and it has been shown that they can arguably replace the classical iterative simulation-based trial/error approaches. Among the most known metaheuristics, Ant Colony Optimization (ACO) has already successfully been used to deal with analog circuit performance optimization. Despite the fact that ACO is robust and has a good intrinsic intensive research strategy, it suffers from its greedy requirement in computation time. In this chapter, the authors deal with the improvement of the ACO technique by integrating in this algorithm a backtracking search technique that has the role to act on the ratio of the accumulated pheromones, thus reducing the computation time. The new algorithm is called BA-ACO. Performances of BA-ACO are highlighted through some RF-applications. ADS simulation results are given to show the validity of the proposed algorithm.
TopIntroduction
Integrated circuit (IC) design is a complicated and delicate process. The design of the analog part is often the most difficult, tedious and time consuming task in the entire design. This is mainly due to the fact that the design of the digital part has already been automated, but this is not the case for the analog/RF part where such design lacks for fully automated procedures. Thus, analog, and particularly the radio-frequency circuit design has long been highly based on the intuition and experience of the skilled designers. Statistical-based techniques have long been used to deal with such designs (Medeiro, 1994). However, these techniques are time consuming and do not guarantee reaching the global optimum solution.
To efficiently deal with such NP-hard optimization problems, metaheuristics were adopted for such purposes. Most considered ones in the field of circuit design were: Tabu Search (TS) (Glover, 1989; 1990), Simulated Annealing (SA) (Dreo, 2006), Genetic Algorithms (GA) (Dreo, 2006; Grimbleby, 2000), Local Search (LS) (Aarts, 2003). Recently, some swarm intelligence (SI) based metaheuristics (Garnier, 2007) were proposed and it has been proven that these ‘new’ techniques are efficient, resourceful, robust, efficient and easy to be implemented and used. Further, they can be, in many applications, much more attractive when compared with their predecessors (see above). A plethora of SI algorithms are proposed in the available literature, most well-known ones may be Wasp Nets (WN) (Chan, 2007), Bacterial Foraging Optimization (BFO) (Chatterjee, 2010), Particle Swarm Optimization (PSO) (Fakhfakh, 2010) and Ant Colony Optimization (ACO) (Benhala, 2011; 2011b).
In the realm of analog circuit sizing, BCO, PSO and ACO were/are widely used, see for instance (Benhala, 2011; 2011b; 2011c; 2012; 2012b; Bennour, 2010; Chatterjeea, 2010 ; Cooren, 2007; Fakhfakh, 2009; 2010; Kotti, 2010). It has already been shown that ACO offers the best optimum quality, when compared to the other SI approaches, see (Kotti, 2012; Sallem, 2013). However, ACO techniques seriously suffer from their greedy need in computation time. Actually, this is due to their ‘graph-based’ search mechanism and to the use/update of the routing search.
Ant Colony Optimization (ACO) is an evolutionary stochastic computational technique for solving hard combinatorial optimization problems (Dorigo, 1996). ACO imitates the natural behavior of ants in finding the shortest distance between their nests and food sources. It is based on the indirect communication within a colony of simple agents, called (artificial) ants which exchange information about good routes through a chemical substance, called pheromone, that accumulates for short routes and evaporate for long routes (Dorigo, 1999; 2006). Pheromones are the means of communication between ants which directly affects the convergence and the efficient resolution of the ACO algorithm (Daniel, 2003)
The ACO algorithm conducts the search procedure intelligently to perform global optimizations. It is characterized by its robustness, distributed calculation, and the fact that it can be easily combined or hybridized with other optimization algorithms. Therefore, ACO may provide a powerful optimization tool (Colorni, 1991). Some variants of the ACO algorithm have recently been proposed in order to improve performances of the basic ACO technique, for instance the way the pheromone matrix is updated (Dorigo, 1996, 1997), the manner to avoid stagnation on selected edges (Stützle, 2000), etc. However, the slowness of the technique remains the most important limitation of this approach, as stated above.
Recently, a novel enhancement technique, called backtracking, has been proposed. It has been used to improve performances of the PSO technique. Very interesting results were reached; see (Civicioglu, 2013).
In this work we propose the modification of the ACO technique by integrating the backtracking search approach in its algorithm. The main idea consists of dealing, via the backtracking approach, on the one hand with the excessive accumulation of pheromones which may entrap ACO in local optima, and on the other hand with reducing the search space and thus increasing the convergence speed and improves the overall search capability.