Parallel genetic algorithms for the DAG Vertex Splitting Problem

Author

Matthias Mayer

Abstract

"Directed Acyclic Graphs are often used to model circuits and networks. The path length in such Directed Acyclic Graphs represents circuit or network delays. In the vertex splitting problem, the objective is to determine a minimum number of vertices from the graph to split such that the resulting graph has no path of length greater than a given δ. The problem has been proven to be NP-hard.

A Sequential Genetic Algorithm has been developed to solve the DAG Vertex Splitting Problem. Unlike a standard Genetic Algorithm, this approach uses a variable chromosome length to represent the vertices that split the graph and a dynamic population size. Two String Length Reduction Methods to reduce the string length and two Stepping Methods to explore the search space have been developed. Combinations of these four methods have been studied and conclusions are drawn.

A parallel version of the sequential Genetic Algorithm has been developed. It uses a fully distributed scheme to assign different string lengths to processors. A ring exchange method is used in order to exchange "good" individuals between processors. Almost linear speed-up and two cases of super linear speed-up are reported"--Abstract, page iii.

Advisor(s)

Erçal, Fikret

Committee Member(s)

Prater, John Bruce, 1932-2002
Patel, J.

Department(s)

Computer Science

Degree Name

M.S. in Computer Science

Comments

A report which is substantially this thesis is available here for download.

Publisher

University of Missouri--Rolla

Publication Date

Spring 1993

Pagination

xii, 91 pages

Note about bibliography

Includes bibliographical references (pages 88-90).

Rights

© 1993 Matthias Mayer, All rights reserved.

Document Type

Thesis - Restricted Access

File Type

text

Language

English

Thesis Number

T 6573

Print OCLC #

28767868

Link to Catalog Record

Electronic access to the full-text of this document is restricted to Missouri S&T users. Otherwise, request this publication directly from Missouri S&T Library or contact your local library.

Recommended Citation

Mayer, Matthias, "Parallel genetic algorithms for the DAG Vertex Splitting Problem" (1993). Masters Theses. 1225.
https://scholarsmine.mst.edu/masters_theses/1225