Iterative Computer Algorithms with Applications in Engineering Solving Combinatorial Optimization Problems

by ;
Edition: 1st
Format: Paperback
Pub. Date: 2000-02-10
Publisher(s): Wiley-IEEE Computer Society Pr
List Price: $159.94

Buy New

Usually Ships in 8 - 10 Business Days.
$159.78

Rent Textbook

Select for Price
There was a problem. Please try again later.

Used Textbook

We're Sorry
Sold Out

eTextbook

We're Sorry
Not Available

How Marketplace Works:

  • This item is offered by an independent seller and not shipped from our warehouse
  • Item details like edition and cover design may differ from our description; see seller's comments before ordering.
  • Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
  • Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
  • Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.

Summary

Iterative Computer Algorithms with Applications in Engineering describes in-depth the five main iterative algorithms for solving hard combinatorial optimization problems: Simulated Annealing, Genetic Algorithms, Tabu Search, Simulated Evolution, and Stochastic Evolution. The authors present various iterative techniques and illustrate how they can be applied to solve several NP-hard problems. For each algorithm, the authors present the procedures of the algorithm, parameter selection criteria, convergence property analysis, and parallelization. There are also several real-world examples that illustrate various aspects of the algorithms. The book includes an introduction to fuzzy logic and its application in the formulation of multi-objective optimization problems, a discussion on hybrid techniques that combine features of heuristics, a survey of recent research work, and examples that illustrate required mathematical concepts. The unique features of this book are: An integrated and up-to-date description of iterative non-deterministic algorithms; Detailed descriptions of Simulated Evolution and Stochastic Evolution; A level of treatment suitable for first year graduate student and practicing engineers; Parallelization aspects and particular parallel implementations; A brief survey of recent research work; Graded exercises and an annotated bibliography in each chapter

Author Biography

Sadiq M. Sait obtained a Bachelor's degree in Electronics from Bangalore University, India, in 1981, and master's and Ph.D. degrees in Electrical Engineering from King Fahd University of Petroleum and Minerals (KFUPM), Dhahran, in 1983 and 1987, respectively. He is currently a professor in the Department of Computer Engineering of KFUPM. Sait has authored over 85 research papers in international journals and conferences. He is coauthor of the book VLSI Physical Design Automation: Theory and Practice, published in January 1995. He has also contributed two chapters to a book entitled Progress in VLSI design. He served on the editorial board of International Journal of Computer-Aided Design between 1988 and 1990. Currently he is the editor of Arabian Journal for Science and Engineering for Computer Science & Engineering. His current areas of interest are in digital design automation, VLSI system design, high-level synthesis, and iterative algorithms. Habib Youssef received a Diplome d'Ingenieur en Informatique from the Faculté des Sciences de Tunis in 1982 and a Ph.D. in Computer Science from the University of Minnesota in 1990. He is currently and Associate Professor of Computer Engineering at King Fahd University of Petroleum and Minerals, Saudi Arabia. Youssef has authored more than 45 journal and conference papers. He is the coauthor of the book VLSI Physical Design Automation: Theory and Practice, January 1995. His main research interests are CAD of VLSI, computer networks, and performance evaluation of computer systems, and general stochastic and evolutionary algorithms.

Table of Contents

Preface xix
Introduction
1(48)
Combinatorial Optimization
1(7)
Complexity of Algorithms
4(2)
Hard Problems versus Easy Problems
6(2)
Optimization Methods
8(2)
States, Moves, and Optimality
10(1)
Local Search
11(4)
Deterministic and Stochastic Algorithms
13(2)
Optimal versus Final Solution
15(1)
Single versus Multicriteria Constrained Optimization
16(2)
Convergence Analysis of Iterative Algorithms
18(2)
Configuration Graph
18(2)
Markov Chains
20(6)
Time-Homogeneous Markov Chains
20(1)
Perturbation Probability
21(1)
Ergodic Markov Chains
21(3)
Acceptance Probability
24(1)
Transition Probability
25(1)
Parallel Processing
26(3)
Summary and Organization of the Book
29(20)
References
33(3)
Exercises
36(13)
Simulated Annealing (SA)
49(60)
Introduction
49(4)
Background
50(3)
Simulated Annealing Algorithm
53(4)
SA Convergence Aspects
57(9)
Parameters of the SA Algorithm
66(7)
A Simple Cooling Schedule
67(1)
A Statistical Polynomial Time Cooling Schedule
68(4)
An Efficient General Cooling Schedule
72(1)
SA Requirements
73(2)
SA Applications
75(6)
VLSI Placement and Timber Wolf3.2
75(5)
A Brief Overview of Other Applications
80(1)
Parallelization of SA
81(10)
Parallel Annealing
82(1)
Multiple-Trials Parallelism
83(8)
Conclusions and Recent Work
91(18)
References
93(5)
Exercises
98(11)
Genetic Algorithms (GAs)
109(74)
Introduction
109(10)
GA Basics
110(1)
GA Terminology
111(8)
Genetic Algorithm
119(1)
Schema Theorem and Implicit Parallelism
119(7)
Schema Theorem
122(3)
Implicit Parallelism
125(1)
GA Convergence Aspects
126(4)
GA without Mutation or Inversion
127(1)
GA with Crossover and Mutation
128(2)
GA in Practice
130(12)
Genetic Operators
131(6)
Scoring/Fitness Function
137(1)
Scaling
138(1)
Selection of Parents
139(3)
Parameters of GAs
142(4)
Population
142(1)
Generation Gap
143(1)
Operator Probabilities
144(1)
Other Issues
145(1)
Applications of GAs
146(10)
Traveling Salesman Problem
147(4)
Module Placement
151(2)
Applications of GAs to Other Problems
153(3)
Parallelization of GA
156(2)
Island Model
156(1)
Stepping-Stone Model
157(1)
Neighborhood or Cellular Model
157(1)
Other Issues and Recent Work
158(6)
Performance Measurement
158(1)
Gray versus Binary Encoding
159(1)
Niches, Crowding, and Speciation
159(2)
Constant versus Dynamically Decreasing Population
161(1)
Multiobjective Optimization with GAs
162(1)
Other Related Material
163(1)
Conclusions
164(19)
References
165(8)
Exercises
173(10)
Tabu Search (TS)
183(70)
Introduction
183(2)
Tabu Search Algorithm
185(9)
Implementation-Related Issues
194(12)
Move Attributes
194(1)
Tabu List and Tabu Restrictions
195(3)
Data Structure to Handle Tabu Lists
198(6)
Other Aspiration Criteria
204(2)
Limitations of Short-Term Memory
206(5)
Intermediate-Term Memory (Search Intensification)
207(1)
Long-Term Memory (Search Diversification)
208(3)
Examples of Diversifying Search
211(4)
Diversification in Quadratic Assignment (QAP)
211(3)
Diversification in Multiprocessor Scheduling
214(1)
TS Convergence Aspects
215(2)
TS Applications
217(5)
QAP Problem
218(2)
Bandwidth Packing Problem (BWP)
220(2)
Parallelization of TS
222(6)
Other Issues and Related Work
228(12)
Neighborhood, Evaluator Functions, Stopping Criteria
228(2)
Target Analysis (TA)
230(4)
Candidate List Strategies
234(3)
Strategic Oscillation
237(2)
Path Relinking
239(1)
Conclusions
240(13)
References
242(6)
Exercises
248(5)
Simulated Evolution (SimE)
253(46)
Introduction
253(1)
Historical Background
254(1)
Simulated Evolution Algorithm
254(10)
Evaluation
258(3)
Selection
261(1)
Sorting
262(1)
Allocation
262(2)
Initialization Phase
264(1)
SimE Operators and Parameters
264(2)
Effect of Selection
265(1)
Effect of Allocation
265(1)
Effect of Number of Populations
266(1)
Effect of Number of Iterations
266(1)
Comparison of SimE, SA, and GA
266(2)
SimE Convergence Aspects
268(3)
SimE Applications
271(13)
Standard-Cell Design Style
271(12)
Other Applications of SimE
283(1)
Parallelization of SimE
284(4)
Implementation of SimE on Vector Processors
284(2)
Implementation of SimE on MISD and MIMD Machines
286(2)
Conclusions and Recent Work
288(11)
References
289(3)
Exercises
292(7)
Stochastic Evolution (StocE)
299(46)
Introduction
299(1)
Historical Background
300(1)
Stochastic Evolution Algorithm
301(8)
StocE Algorithm
304(3)
StocE versus SA
307(1)
StocE versus SimE
308(1)
Stochastic Evolution Convergence Aspects
309(3)
Stochastic Evolution Applications
312(20)
Network Bisection
312(1)
Vertex Cover Problem
312(3)
Hamiltonian Circuit Problem
315(4)
Traveling Salesman Problem
319(1)
StocE-Based Technology Mapping of FPGAs
320(12)
Parallelization of Stochastic Evolution
332(5)
Conclusions and Recent Work
337(8)
References
338(3)
Exercises
341(4)
Hybrids and Other Issues
345(34)
Introduction
345(1)
Overview of Algorithms
346(2)
Hybridization
348(4)
SA/TS Hybrid
348(1)
GA/SA Hybrid
349(2)
Other Hybrids
351(1)
GA and Multiobjective Optimization
352(4)
Pareto Optimality
353(1)
VEGA
354(1)
MOGA
354(2)
Fuzzy Logic for Multiobjective Optimization
356(6)
Fuzzy Set Theory
356(2)
Fuzzy Operators
358(1)
Fuzzy Rules
358(1)
Example of Fuzzy Multiobjective Optimization
359(2)
Fuzzy Goal Directed Optimization
361(1)
Artificial Neural Networks
362(5)
Quality of the Solution
367(3)
Conclusions
370(9)
References
372(4)
Exercises
376(3)
About the Authors 379(2)
Index 381

An electronic version of this book is available through VitalSource.

This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.

By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.

Digital License

You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.

More details can be found here.

A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.

Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.

Please view the compatibility matrix prior to purchase.