Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Preliminary Study on Impact of Dying of Solution on Performance of Multi-objective Genetic Algorithm Read chapter Read first chapter

2014 | OriginalPaper | Chapter

Strongly Biased Crossover Operator for Subgraph Selection in Edge-Set Based Graph Representation

Authors : Sakshi Arora, M. L. Garg

Published in: Proceedings of the Third International Conference on Soft Computing for Problem Solving

Publisher: Springer India

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The performance of crossover operator is a complex interplay of the various characteristics of the genetic algorithm (GA) and sometimes also of the problem under question. The fundamental design choices in a GA therefore, are its representation of candidate solutions and the operators that will act on that representation. This paper suggests a new strongly biased multiparent crossover operator that offers a strong locality and provides a strong heritability quotient but can still escape the local optima when the sample space is over represented by similar building blocks. The proposed operator uses a dynamic 2-D vector representation for the chromosomes and this data structure may evolve as the execution of the crossover operator proceeds. On a population which consists of solutions near to optimal and mostly lying in the basin of attraction of single optima, the bias towards the optima in the generated offsprings is proportional to the sample size from the search space. Based on this reasoning, the effect of arity of the proposed crossover operator is tested using a population in which all the candidates lie in close neighborhood of each other. To analyze the dynamic search behavior of the proposed crossover operator and the impact of the representation scheme on the locality, heritability and exploratory power of the operator, we suggest a no mutation, zero selection pressure GA model that generates bounded diameter minimum spanning trees from the underlying complete graphs on random and Euclidean instances.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Local Search Methods for the Winner Determination Problem in Multi-Unit Combinatorial Auctions
next chapter “Color to Gray and Back” Using DST-DCT, Haar-DCT, Walsh-DCT, Hartley-DCT, Slant-DCT, Kekre-DCT Hybrid Wavelet Transforms
Literature
1.
Raidl, G.R., Julstrom, B.A.: Edge sets: an effective evolutionary coding of spanning trees. IEEE Trans. Evol. Comput. 7(3), 225–239 (2003)CrossRef
2.
Fekete, S.P., et al.: A network-flow technique for finding low-weight bounded-degree spanning trees. J. Algorithms 24.2, 310–324 (1997)
3.
Julstrom, B.A., Raidl, G.R.: A permutation-coded evolutionary algorithm for the bounded-diameter minimum spanning tree problem. In: Workshop on Analysis and Design of Representations in 2003 Genetic and Evolutionary Computation Conference’s Workshops Proceedings, pp. 2–7 (2003)
4.
Gen, M., Ida, K., Kim, J.: A spanning tree-based genetic algorithm for bicriteria topological network design. In: Evolutionary Computation Proceedings, 1998. The 1998 IEEE International Conference on IEEE World Congress on Computational Intelligence, pp. 15–20. IEEE (1998)
5.
Rothlauf, F.: On the bias and performance of the edge-set encoding. IEEE Trans. Evol. Comput. 13(3), 486–499 (2009)CrossRef
6.
Rothlauf, F., Tzschoppe, C.: Making the edge-set encoding fly by controlling the bias of its crossover operator, pp. 202–212. Springer, Berlin (2005)
7.
Tsutsui, S.: Sampling bias and search space boundary extension in real coded genetic algorithms. In GECCO, pp. 211–218 (2000)
8.
Srinivas, M., Patnaik, L.M.: Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans. Syst. Man Cybernet. 24(4), 656–667 (1994)CrossRef
9.
Julstrom, B.A.: Encoding rectilinear Steiner trees as lists of edges. In: Proceedings of the 2001 ACM Symposium on Applied Computing ACM, pp. 356–360 (2001)
10.
Li, Y.: An effective implementation of a direct spanning tree representation in GAs. In: Applications of Evolutionary Computing, pp. 11–19. Springer, Berlin (2001)
11.
Julstrom, B.A., Raidl, G.R.: Weight-biased edge-crossover in evolutionary algorithms for two graph problems. In: Proceedings of the 2001 ACM Symposium on Applied Computing, pp. 321–326 (2001)
12.
Kaufman, H.: An experimental investigation of process identification by competitive evolution. IEEE Trans. Syst. Sci. Cybernet. 3(1), 11–16 (1967)CrossRef
13.
Mühlenbein, H.: Parallel genetic algorithms, population genetics and combinatorial optimization. In: Parallelism, Learning, Evolution, pp. 398–406. Springer, Berlin (1991)
14.
Bersini, H., Seront, G.: In search of a good crossover between evolution and optimization. Manner Manderick 1503, 479–488 (1992)
15.
Aizawa, A.N.: Evolving SSE: a stochastic schemata exploiter. In: Proceedings of the 1st IEEE Conference on Evolutionary Computation, pp. 525–529. IEEE Press (1994)
16.
Eiben, A.E., Raue, P.E., Ruttkay, Z.: Genetic algorithms with multi-parent recombination. In: Parallel Problem Solving from Nature—PPSN III, pp. 78–87. Springer, Berlin (1994)
17.
Tsutsui, S.: Multi-parent recombination in genetic algorithms with search space boundary extension by mirroring. In: Parallel Problem Solving from Nature—PPSN V. Springer, Berlin (1998)
18.
Knowles, J., Corne, D.: A new evolutionary approach to the degree-constrained minimum spanning tree problem. IEEE Trans. Evol. Comput. 4(2), 125–134 (2000)CrossRef
19.
Deo, N., Abdalla, A.: Computing a diameter-constrained minimum spanning tree in parallel. In: Algorithms and Complexity, pp. 17–31. Springer, Berlin (2000)
20.
Arora, S., Garg, M.L.: New hybrid evolutionary algorithm for solving the bounded diameter minimum spanning tree problem (2009)
21.
Arora, S., Garg, M.L.: Clustering the data points to obtain optimum backbones for the bounded diameter minimum spanning trees. In: 2011 International Conference on Communication Systems and Network Technologies (CSNT), pp. 303–307. IEEE (2011)
22.
Arora, S., Garg, M.L.: Neighborhood search for the bounded diameter minimum spanning tree. Int. J. Emerg. Technol. Adv. Eng. 3(2) (2013)
23.
Kopinitsch, B.: An ant colony optimisation algorithm for the bounded diameter minimum spanning tree problem. Vienna University of Technology, Institute of Computer Graphics and Algorithms (2006)
24.
Gruber, M., Raidl, G.R.: Variable neighborhood search for the bounded diameter minimum spanning tree problem. PhD thesis, Institute of Computer Graphics and Algorithms, Vienna University of Technology, pp. 1187–1194 (2006)
Metadata
Title
Strongly Biased Crossover Operator for Subgraph Selection in Edge-Set Based Graph Representation
Authors
Sakshi Arora
M. L. Garg
Copyright Year
2014
Publisher
Springer India
Book
Proceedings of the Third International Conference on Soft Computing for Problem Solving

Print ISBN: 978-81-322-1767-1

Electronic ISBN: 978-81-322-1768-8

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-81-322-1768-8_53

Premium Partner

    Image Credits