skip to main content
10.1145/1389095.1389268acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

Search space reduction technique for constrained optimization with tiny feasible space

Published: 12 July 2008 Publication History

Abstract

The hurdles in solving Constrained Optimization Problems (COP) arise from the challenge of searching a huge variable space in order to locate feasible points with acceptable solution quality. It becomes even more challenging when the feasible space is very tiny compare to the search space. Usually, the quality of the initial solutions influences the performance of the algorithm in solving such problems. In this paper, we discuss an Evolutionary Agent System (EAS) for solving COPs. In EAS, we treat each individual in the population as an agent. To enhance the performance of EAS for solving COPs with tiny feasible space, we propose a Search Space Reduction Technique (SSRT) as an initial step of our algorithm. SSRT directs the selected infeasible agents in the initial population to move towards the feasible space. The performance of the proposed algorithm is tested on a number of test problems and a real world case problem. The experimental results show that SSRT not only improves the solution quality but also speed up the processing time of the algorithm.

References

[1]
Barkat Ullah, A. S. S. M., Sarker, R., and Cornforth, D. A Combined MA-GA Approach for Solving Constrained Optimization Problems, in Computer and Information Science, 2007. ICIS 2007. 6th IEEE/ACIS International Conference on (2007),2007. 382--387.
[2]
Barkat Ullah, A. S. S. M., Sarker, R., and Cornforth, D. An Evolutionary Agent System for Mathematical Programming. in Advances in Computation and Intelligence: Springer, 2007, 187--196.
[3]
Barkat Ullah, A. S. S. M., Sarker, R., Cornforth, D., and Lokan, C. An Agent-based Memetic Algorithm (AMA) for Solving Constrained Optimization Problems, in Evolutionary Computation, 2007. CEC 2007. IEEE Congress on (2007),2007. 999--1006.
[4]
Chootinan, P. and Chen, A. Constraint handling in genetic algorithms using a gradient-based repair method. Computers & Operations Research, 33, 8, (2006). 2263--2281.
[5]
Coello Coello, C. A. Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art. Computer Methods in Applied Mechanics and Engineering, 191, 11-12, (2002). 1245--1287.
[6]
Deb, K. An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering, 186, 2--4, (2000). 311.
[7]
Deb, K. Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., 2001.
[8]
Deb, K. and Agrawal, R. B. Simulated Binary Crossover for Continuous Search Space. Complex Systems, 9,1995). 115--148.
[9]
Dobrowolski, G., Kisiel-Dorohinicki, M., and Nawarecki, E. Evolutionary multiagent system in multiobjective optimisation, in Proc. of the IASTED Int. Symp.: Applied Informatics (2001), IASTED/ACTA Press., 2001.
[10]
Dre|ewski, R. and Marek, K.--D. Maintaining Diversity in Agent-Based Evolutionary Computation. in Lecture Notes in Computer Science : Computational Science ICCS, 2006, 908--911.
[11]
Farmani, R. and Wright, J. A. Self-adaptive fitness formulation for constrained optimization. Evolutionary Computation, IEEE Transactions on, 7, 5, (2003). 445.
[12]
Ferber, J. Multiagent systems as introduction to distributed artificial intelligence, Addision-Wesley, 1999.
[13]
Goldberg, D. Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989.
[14]
Koziel, S. and Michalewicz, Z. Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization. Evolutionary Computation, 7, 1, (1999),
[15]
Liang, J. J., Runarsson, T. P., Mezura-Montes, E., Clerc, M., Suganthan, P. N., Coello, C. A. C., and Deb, K. Problem Definitions and Evaluation Criteria for the CEC 2006 Special Session on Constrained Real-Parameter Optimization, Nanyang Technological University, http://www.ntu.edu.sg/home/epnsugan/, Singapore 2006.
[16]
Liang, J. J. and Suganthan, P. N. Dynamic Multi-Swarm Particle Swarm Optimizer with a Novel Constraint-Handling Mechanism, in Evolutionary Computation, 2006. CEC 2006. IEEE Congress on (2006),2006. 9--16.
[17]
Liu, J., Zhong, W., and Jiao, L. A multiagent evolutionary algorithm for constraint satisfaction problems. Systems, Man and Cybernetics, Part B, IEEE Transactions on, 36, 1, (2006). 54--73.
[18]
Michalewicz, Z. Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, 1994.
[19]
Michalewicz, Z. and Janikow, C. Z. GENOCOP: a genetic algorithm for numerical optimization problems with linear constraints. Communications of the ACM, 39,1996),
[20]
Michalewicz, Z. and Schoenauer, M. Evolutionary algorithms for constrained parameter optimization problems. Evolutionary Computation, 4, 1, (1996). 1--32.
[21]
Ong, Y. S. and Keane, A. J. Meta-Lamarckian learning in memetic algorithms. Evolutionary Computation, IEEE Transactions on, 8, 2, (2004). 99--110.
[22]
Runarsson, T. P. and Yao, X. Stochastic ranking for constrained evolutionary optimization. Evolutionary Computation, IEEE Transactions on, 4, 3, (2000). 284.
[23]
Sarker, R. and Quaddus, M. Modelling a Nationwide Crop Planning Problem Using a Multiple Criteria Decision Making Tool. Computers and Industrial Engineering, 42(2-4), pp541--553.,2002),
[24]
Sarker, R. and Ray, T. Multiobjective Evolutionary Algorithms for solving Constrained Optimization Problems, in International Conference on Computational Intelligence for Modelling, Control and Automation (CIMCA2005) (Vienna, Austria.,28 - 30 November 2005,2005), IEEE Press-USA, 2005. Pages.
[25]
Sarker, R. A., Talukder, S., and Haque, A. Determination of Optimum Crop-Mix for Crop Cultivation in Bangladesh. Applied Mathematical Modelling 21,1997). 621--632.
[26]
Siwik, L. and Kisiel-Dorohinicki, M. Semi-elitist Evolutionary Multi-agent System for Multiobjective Optimization. in Lecture Notes in Computer Science : Computational Science ICCS, 2006, 831--838.
[27]
Zhong, W., Liu, J., Xue, M., and Jiao, L. A multiagent genetic algorithm for global numerical optimization. Systems, Man and Cybernetics, Part B, IEEE Transactions on, 34, 2, (2004). 1128--1141.

Cited By

View all
  • (2024)A lattice-based method for optimization in continuous spaces with genetic algorithmsActa Astronautica10.1016/j.actaastro.2024.12.032Online publication date: Dec-2024
  • (2022)A Voting-Mechanism-Based Ensemble Framework for Constraint Handling TechniquesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.311013026:4(646-660)Online publication date: Aug-2022
  • (2022)Towards a machine learning-aided metaheuristic framework for a production/distribution system design problemComputers and Operations Research10.1016/j.cor.2022.105897146:COnline publication date: 1-Oct-2022
  • Show More Cited By

Index Terms

  1. Search space reduction technique for constrained optimization with tiny feasible space

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation
      July 2008
      1814 pages
      ISBN:9781605581309
      DOI:10.1145/1389095
      • Conference Chair:
      • Conor Ryan,
      • Editor:
      • Maarten Keijzer
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 12 July 2008

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. agent-based systems
      2. constrained optimization
      3. evolutionary agent systems
      4. evolutionary algorithms
      5. genetic algorithms
      6. nonlinear programming
      7. search space reduction

      Qualifiers

      • Research-article

      Conference

      GECCO08
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)9
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 09 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)A lattice-based method for optimization in continuous spaces with genetic algorithmsActa Astronautica10.1016/j.actaastro.2024.12.032Online publication date: Dec-2024
      • (2022)A Voting-Mechanism-Based Ensemble Framework for Constraint Handling TechniquesIEEE Transactions on Evolutionary Computation10.1109/TEVC.2021.311013026:4(646-660)Online publication date: Aug-2022
      • (2022)Towards a machine learning-aided metaheuristic framework for a production/distribution system design problemComputers and Operations Research10.1016/j.cor.2022.105897146:COnline publication date: 1-Oct-2022
      • (2019)QoS Preservation in Web Service SelectionTransactions on Computational Collective Intelligence XXXIII10.1007/978-3-662-59540-4_4(71-88)Online publication date: 21-Jun-2019
      • (2017)Search space reduction approach in evolutionary algorithms: The case of high-dimensional portfolio replication problem2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC)10.1109/SMC.2017.8122664(554-559)Online publication date: Oct-2017
      • (2017)Reduced search space mechanism for solving constrained optimization problemsEngineering Applications of Artificial Intelligence10.1016/j.engappai.2017.07.01865:C(147-158)Online publication date: 1-Oct-2017
      • (2017)An experimental analysis of a new two-stage crossover operator for multiobjective optimizationSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-015-1810-621:3(721-751)Online publication date: 1-Feb-2017
      • (2014)An empirical comparison of two crossover operators in real-coded genetic algorithms for constrained numerical optimization problems2014 IEEE International Autumn Meeting on Power, Electronics and Computing (ROPEC)10.1109/ROPEC.2014.7036347(1-5)Online publication date: Nov-2014
      • (2013)Empowering the Performance of Advanced NMPC by Multiparametric Programming—An Application to a PEM Fuel Cell SystemIndustrial & Engineering Chemistry Research10.1021/ie303477h52:13(4863-4873)Online publication date: 22-Mar-2013
      • (2013)Adaptive Configuration of evolutionary algorithms for constrained optimizationApplied Mathematics and Computation10.1016/j.amc.2013.07.068222(680-711)Online publication date: 1-Oct-2013
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media