Handbook Genetic Algorithms.pdf

(11684 KB) Pobierz

The Practical

Handbook of

GENETIC

ALGORITHMS

Applications

SECOND EDITION

The Practical

Handbook of

GENETIC

ALGORITHMS

Applications

SECOND EDITION

Edited by

Lance Chambers

CHAPMAN & HALL/CRC

Boca Raton London New York Washington, D.C.

Library of Congress Cataloging-in-Publication Data

The practical handbook of genetic algorithms, applications / edited by

Lance D. Chambers.—2nd ed.

p. cm.

Includes bibliographical references and index.

ISBN 1-58488-2409-9 (alk. paper)

1. Genetic algorithms. I. Chambers, Lance.

QA402.5 .P72 2000

519.7—dc21

00-064500

CIP

This book contains information obtained from authentic and highly regarded sources. Reprinted material

is quoted with permission, and sources are indicated. A wide variety of references are listed. Reasonable

efforts have been made to publish reliable data and information, but the author and the publisher cannot

assume responsibility for the validity of all materials or for the consequences of their use.

Neither this book nor any part may be reproduced or transmitted in any form or by any means, electronic

or mechanical, including photocopying, microﬁlming, and recording, or by any information storage or

retrieval system, without prior permission in writing from the publisher.

internal use of speciﬁc clients, may be granted by CRC Press LLC, provided that $.50 per page

photocopied is paid directly to Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923

USA. The fee code for users of the Transactional Reporting Service is ISBN 1-58488-240-

9/01/$0.00+$.50. The fee is subject to change without notice. For organizations that have been granted

a photocopy license by the CCC, a separate system of payment has been arranged.

The consent of CRC Press LLC does not extend to copying for general distribution, for promotion, for

creating new works, or for resale. Speciﬁc permission must be obtained in writing from CRC Press LLC

for such copying.

Direct all inquiries to CRC Press LLC, 2000 N.W. Corporate Blvd., Boca Raton, Florida 33431.

Trademark Notice:

Product or corporate names may be trademarks or registered trademarks, and are

used only for identiﬁcation and explanation, without intent to infringe.

No claim to original U.S. Government works

International Standard Book Number 1-58488-240-9

Library of Congress Card Number 00-064500

Printed in the United States of America 1 2 3 4 5 6 7 8 9 0

Printed on acid-free paper

Preface

Bob Stern of CRC Press, to whom I am indebted, approached me in late 1999

asking if I was interested in developing a second edition of volume I of the

Practical Handbook of Genetic Algorithms.

My immediate response was an

unequivocal “Yes!” This is the fourth book I have edited in the series and each

time I have learned more about GAs and people working in the field. I am proud

to be associated with each and every person with whom I have dealt with over the

years. Each is dedicated to his or her work, committed to the spread of knowledge

and has something of significant value to contribute.

This second edition of the first volume comes a number of years after the

publication of the first. The reasons for this new edition arose because of the

popularity of the first edition and the need to perform a number of functions for

the GA community. These “functions” fall into two main categories: the need to

keep practitioners abreast of recent discoveries/learning in the field and to very

specifically update some of the best chapters from the first volume.

The book leads off with chapter 0, which is the same chapter as the first edition

by Jim Everett on model building, model testing and model fitting. An excellent

“How and Why.” This chapter offers an excellent lead into the whole area of

models and offers some sensible discussion of the use of genetic algorithms,

which depends on a clear view of the nature of quantitative model building and

testing. It considers the formulation of such models and the various approaches

that might be taken to fit model parameters. Available optimization methods are

discussed, ranging from analytical methods, through various types of hill-

climbing, randomized search and genetic algorithms. A number of examples

illustrate that modeling problems do not fall neatly into this clear-cut hierarchy.

Consequently, a judicious selection of hybrid methods, selected according to the

model context, is preferred to any pure method alone in designing efficient and

effective methods for fitting parameters to quantitative models.

Chapter 1 by Roubos and Setnes deals with the automatic design of fuzzy rule-

based models and classifiers from data. It is recognized that both accuracy and

transparency are of major importance and we seek to keep the rule-based models

small and comprehensible. An iterative approach for developing such fuzzy rule-

based models is proposed. First, an initial model is derived from the data.

Subsequently, a real-coded GA is applied in an iterative fashion, together with a

rule-based simplification algorithm to optimize and simplify the model,

respectively. The proposed modeling approach is demonstrated for a system

identification and a classification problem. Results are compared to other

approaches in the literature. The proposed modeling approach is more compact

and interpretable.

Goldberg and Hammerham in Chapter 2, have extended their contribution to

Volume III of the series (Chapter 6, pp 119–238) by describing their current

research, which applies this technology to a different problem area, designing

automata that can recognize languages given a list of representative words in the

language and a list of other words not in the language. The experimentation

carried out indicates that in this problem domain also, smaller machine solutions

are obtained by the MTF operator than the benchmark. Due to the small variation

of machine sizes in the solution spaces of the languages tested (obtained

empirically by Monte Carlo methods), MTF is expected to find solutions in a

similar number of iterations as the other methods. While SFS obtained faster

convergence on more languages than any other method, MTF has the overall best

performance based on a more comprehensive set of evaluation criteria.

Taplin and Qiu, in Chapter 3, have contibuted material that very firmly grounds

GA in solving real-world problems by employing GAs to solve the very complex

problems associated with the staging of road construction projects. The task of

selecting and scheduling a sequence of road construction and improvement

projects is complicated by two characteristics of the road network. The first is that

the impacts and benefits of previous projects are modified by succeeding ones

because each changes some part of what is a highly interactive network. The

change in benefits results from the choices made by road users to take advantage

of whatever routes seem best to them as links are modified. The second problem

is that some projects generate benefits as they are constructed, whereas others

generate no benefits until they are completed.

There are three general ways of determining a schedule of road projects. The

default method has been used to evaluate each project as if its impacts and

benefits would be independent of all other projects and then to use the resulting

cost-benefit ratios to rank the projects. This is far from optimal because the

interactions are ignored. An improved method is to use rolling or sequential

assessment. In this case, the first year’s projects are selected, as before, by

independent evaluation. Then all remaining projects are reevaluated, taking

account of the impacts of the first-year projects, and so on through successive

years. The resulting schedule is still sub-optimal but better than the simple

ranking.

Another option is to construct a mathematical program. This can take account of

some of the interactions between projects. In a linear program, it is easy to specify

relationships such as a particular project not starting before another specific

project or a cost reduction if two projects are scheduled in succession. Fairly

simple traffic interactions can also be handled but network-wide traffic effects

have to be analysed by a traffic assignment model (itself a complex programming

task). Also, it is difficult to cope with deferred project benefits. Nevertheless,

Plik z chomika:

musli_com

Handbook Genetic Algorithms.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: