Commonality-Based Local Search
Local search techniques (e.g. hill climbing, simulated annealing, tabu search, genetic algorithms, evolutionary strategies, etc) all employ change operators. A change operator creates a new candidate solution from an existing candidate solution(s) by keeping some parts and changing some parts. Most change operators focus on what is changed -- e.g. a two-opt swap targets two edges to be changed. However, what is kept can also have an important effect on search performance.
The commonality hypothesis suggests that the common components of above-average solutions are above average -- these parts of the solution should be kept. By restricting changes to the uncommon components, the likelihood of an improving change can be increased. Embedded within the change operator, the benefits of preserving common components are independent of the control and selection strategies of the local search technique. These benefits have been isolated and demonstrated in genetic algorithms and simulated annealing.
Evolution Strategies, and Coarse Search-Greedy Search Combinations
I am currently working with Acoustic Ideas Inc. to develop improved optimization techniques for use with their Continuum Probe Designer™. Details on this project appear in the following.Peer-Reviewed Conference Proceedings
S.Chen, S. Razzaqi, and V. Lupien. (2007) “Towards the Automated Design of Phased Array Ultrasonic Transducers -- Using Particle Swarms to find "Smart" Start Points.” In Lecture Notes in Computer Science, Vol. 4570 : Proceedings of the 20th International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, pgs 313-323. Springer. (presentation slides)
S. Chen, S. Razzaqi, and V. Lupien. (2006) “An Evolution Strategy for Improving the Design of Phased Array Transducers.” In Proceedings of the 2006 IEEE Congress on Evolutionary Computation, pgs 2859 - 2863. IEEE. (presentation slides)
Conference Presentations
V. Lupien, S. Chen, S. Razzaqi. (2006) “Recent Advances in Automatic Phased Array Transducer Geometrical Design.” American Society for Nondestructive Testing, 15th Annual Research Symposium, Orlando, FL. March 2006.
Simulated Annealing
The preservation of common components has been incorporated into a single-parent change operator and isolated from the control and selection strategies of genetic algorithms. The benefits of preserving commonality have led to significant improvements for a simulated annealing application on the TSP.
Source Code
The linked C++ source code was used to develop the results presented in "The Coordination of Parallel Search with Common Components."
SAGA has been developed in Java. All source may be used freely for academic purposes. SAGA uses the York package for input and output functions.
TSP instances are taken from TSPLIB, but are modified to have city coordinates at the top of the file.
Peer-Reviewed Conference Proceedings
S. Chen. (2006) "A Little Respect (for the Role of Common Components in Heuristic Search)." In IFIP International Federation for Information Processing, Volume 218, Professional Practice in Artificial Intelligence, pgs 71-80. Springer. (presentation slides)
S. Chen and G. Pitt. (2005) “The Coordination of Parallel Search with Common Components.” In Lecture Notes in Computer Science, Vol. 3533 : Proceedings of the 18th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems. pgs 619-627. © Springer-Verlag. (presentation slides) -- Best Paper Award Candidate
S. Chen and G. Pitt. (2005) "Isolating the Benefits of Respect." In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO-2005. pgs 1601-1602. ACM Press. <full-length version>
Working Papers
S. Chen. (2003) "SAGA: Demonstrating the Benefits of Commonality-Based Crossover Operators in Simulated Annealing." School of Analytical Studies and Information Technology, York University.
Genetic Algorithms
Commonality-based local search was developed from my previous research in genetic algorithms. Please see the following papers for more information. The "Commonality-Based Selection" paper presents the best overall summary of the key concepts.Peer-Reviewed Book Chapters
S. Chen and S.F. Smith. (1999) "Putting the "Genetics" back into Genetic Algorithms (Reconsidering the Role of Crossover in Hybrid Operators)." In Foundations of Genetic Algorithms 5, W. Banzhaf and C. Reeves, eds. Morgan Kaufmann. pgs 103-116.
(Note: this material is also available in Chapter 7 of my PhD thesis.)
Peer-Reviewed Conference Proceedings
S. Chen and S.F. Smith. (1999) "Introducing a New Advantage of Crossover: Commonality-Based Selection." In GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference. pgs 122-128.
S. Chen and S.F. Smith. (1999) "Improving Genetic Algorithms by Search Space Reductions (with Applications to Flow Shop Scheduling)." In GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference. pgs 135-140.
S. Chen, C. Guerra-Salcedo, and S.F. Smith. (1999) "Non-Standard Crossover for a Standard Representation -- Commonality-Based Feature Subset Selection." In GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference. pgs 129-134.
S. Chen, S.F. Smith, and C. Guerra-Salcedo. (1999) "The GENIE is Out! (Who Needs Fitness to Evolve?)." In CEC99: Proceedings of the Congress on Evolutionary Computation. pgs 2102-2108.
C. Guerra-Salcedo, S. Chen, L.D. Whitley, and S.F. Smith. (1999) "Fast and Accurate Feature Selection Using Hybrid Genetic Strategies." In CEC99: Proceedings of the Congress on Evolutionary Computation. pgs 177-184.
S. Chen, S. Talukdar, and N. Sadeh-Koniecpol. (1993) "Job Shop Scheduling by an Asynchronous Team of Optimization Agents." In Proceedings of the IJCAI-93 Workshop on Knowledge-based Production Planning, Scheduling, and Control, August, 1993.
Technical Reports
S. Chen and S.F. Smith. (1996) “Commonality and Genetic Algorithms.” tech. report CMU-RI-TR-96-27, Robotics Institute, Carnegie Mellon University, December, 1996.
Other Information
This research has been funded in part by the Natural Sciences and Engineering Research Council of Canada.
I am a member of the International Society of Applied Intelligence.
