Article

Improving GA search reliability using maximal hyper-rectangle analysis

Authors:

Chongshan Zhang,

Khaled RasheedAuthors Info & Claims

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

Pages 1185 - 1192

https://doi.org/10.1145/1068009.1068205

Published: 25 June 2005 Publication History

Get Access

Abstract

In Genetic algorithms it is not easy to evaluate the confidence level in whether a GA run may have missed a complete area of good points, and whether the global optimum was found. We accept this but hope to add some degree of confidence in our results by showing that no large gaps were left unvisited in the search space. This can be achieved to some extent by inserting new individuals in big empty spaces. However it is not easy to find the biggest empty spaces, particularly in multi-dimensional problems. For a GA problem, however, it is not necessary to find the exact biggest empty spaces; a sufficiently large empty space is good enough to insert new individuals. In this paper, we present a method to find a sufficiently large empty Hyper-Rectangle for new individual insertion in a GA while keeping the computational complexity as a polynomial function. Its merit is demonstrated in several domains.

References

[1]

Ku, L., Liu, B., and Hsu, W. Discovering Large Empty Maximal Hyper-Rectangle in Multi-Dimensional Space. Technical Report, Department of Information Systems and Computer Science (DCOMP), National University of Singapore, 1997.]]

Google Scholar

[2]

Liu, B., Ku, L., and Hsu, W. Discovering Interesting Holes in Data. In Proceedings of IJCAI, pages930--935, Nagoya, Japan, 1997.]]

Digital Library

Google Scholar

[3]

Edmonds, J., Cryz, J., Liang, D., and Miller, R. J. Mining for Empty Rectangles in Large Data Sets. In Proceedings of Intl Conf on Database Theory (ICDT), pages 174--188, 2001.]]

Digital Library

Google Scholar

[4]

Liu, B., Wang, K., Mun, L.F., and Qi, X.Z. Using Decision Tree Induction for Discovering Holes in Data. In 5th pacific Rim International Conference on artificial Intelligence, Pages182--193, 1998.]]

Digital Library

Google Scholar

[5]

Bohchevshy, I.O., Johnson, M.E., and Stein, M.L. Generalized Simulated Annealing for Function Optimization. Technometrics 28(3), PP. 209--218, 1986.]]

Digital Library

Google Scholar

[6]

Fogel, D.B. Evolutionary computation: toward a new philosophy of machine intelligence. (Institute of Electrical and Electronics Engineers, Inc.).]]

Digital Library

Google Scholar

[7]

Ballester, P.J. and Carter J.N. Real-parameter Genetic Algorithms for Finding Multiple optimal Solution in Multi-modal Optimization. GECCO 2003, LNCS2723, PP. 706--717, 2003.]]

Digital Library

Google Scholar

[8]

Mahfoud, S. A comparison of parallel and sequential Niching methods. 6th Int. Conf. on Genetic Algorithms, pages 136--143. Morgan--Kaufmann,1996.]]

Digital Library

Google Scholar

[9]

Michalewics, Z. Genetic Algorithms + Data Structures = Evolution Programs. Third Edition, Springer, 1996.]]

Digital Library

Google Scholar

Cited By

View all

LI QMAEDA Y(2009)Fuzzy Adaptive Search Method for Parallel Genetic Algorithm and Its Improved MethodsJournal of Japan Society for Fuzzy Theory and Intelligent Informatics10.3156/jsoft.21.89421:5(894-904)Online publication date: 2009
https://doi.org/10.3156/jsoft.21.894

Index Terms

Improving GA search reliability using maximal hyper-rectangle analysis
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

A new approach to construct near-optimal binary search trees using genetic algorithm
AIAP'07: Proceedings of the 25th conference on Proceedings of the 25th IASTED International Multi-Conference: artificial intelligence and applications

Many definitive and approximate methods have been so far proposed for the construction of an optimal binary search tree. One such method is the use of evolutionary algorithms with satisfactorily improved cost efficiencies. This paper will propose a new ...
Comparative study on VQ with simple GA and ordain GA
ACMOS'07: Proceedings of the 9th WSEAS international conference on Automatic control, modelling and simulation

In the present research we study the codebook generation problem of vector quantization, using two different techniques of Genetic Algorithm (GA). We compared the Simple GA (SGA) method and Ordain GA (OGA) method in vector quantization. SGA with ...
Building a better air defence system using genetic algorithms
KES'06: Proceedings of the 10th international conference on Knowledge-Based Intelligent Information and Engineering Systems - Volume Part I

It is the aim of every country to have a good and strong defence system for the protection of its people and its assets. In this paper we have shown the application of Genetic Algorithms (GA'S) for optimizing the expected survival value of an asset ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computation

June 2005

2272 pages

ISBN:1595930108

DOI:10.1145/1068009

Editor:
Hans-Georg Beyer
Vorarlberg University of Applied Sciences, Austria
,
General Chair:
Una-May O'Reilly
CSAIL, MIT

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO05

Sponsor:

GECCO05: Genetic and Evolutionary Computation Conference

June 25 - 29, 2005

Washington DC, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
190
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

LI QMAEDA Y(2009)Fuzzy Adaptive Search Method for Parallel Genetic Algorithm and Its Improved MethodsJournal of Japan Society for Fuzzy Theory and Intelligent Informatics10.3156/jsoft.21.89421:5(894-904)Online publication date: 2009
https://doi.org/10.3156/jsoft.21.894

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A new approach to construct near-optimal binary search trees using genetic algorithm

Comparative study on VQ with simple GA and ordain GA

Building a better air defence system using genetic algorithms