Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity

روش‌های محاسباتی الهام‌گرفته از زیستی، مانند الگوریتم‌های تکاملی و بهینه‌سازی کلنی مورچه‌ها، با موفقیت برای مسائل پیچیده مهندسی و بهینه‌سازی ترکیبی اعمال می‌شوند، و بسیار مهم است که ما پیچیدگی محاسباتی این اکتشافی‌های جستجو را درک کنیم. این اولین کتابی است که مهم ترین نتایج به دست آمده در این زمینه را توضیح می دهد.

نویسندگان نشان می دهند که چگونه رفتار زمان اجرا را می توان به روشی دقیق تحلیل کرد. به ویژه برای بهینه سازی ترکیبی. آنها مشکلات شناخته شده ای مانند حداقل درختان پوشا، کوتاه ترین مسیرها، حداکثر تطابق و مشکلات پوشش و زمان بندی را ارائه می دهند. بهینه سازی کلاسیک تک هدف ابتدا مورد بررسی قرار می گیرد. آنها سپس پیچیدگی محاسباتی محاسبات الهام‌گرفته از زیستی را بررسی می‌کنند که برای انواع چندهدفه مسائل بهینه‌سازی ترکیبی در نظر گرفته می‌شود، و به ویژه نشان می‌دهند که چگونه بهینه‌سازی چندهدفه می‌تواند به سرعت بخشیدن به محاسبات الهام‌گرفته از زیستی برای مسائل بهینه‌سازی تک‌هدفه کمک کند.

این این کتاب برای دوره های کارشناسی ارشد و پیشرفته در زمینه محاسبات الهام گرفته از زیست ارزشمند خواهد بود، زیرا ارزیابی های واضحی از مزایا و معایب روش های مختلف ارائه می دهد. این یک ارائه مستقل، مبانی نظری تکنیک ها، یک چارچوب یکپارچه برای تجزیه و تحلیل، و توضیحاتی در مورد تکنیک های اثبات رایج ارائه می دهد، بنابراین می تواند به عنوان مرجعی برای محققان در زمینه های محاسبات طبیعی، بهینه سازی و پیچیدگی محاسباتی استفاده شود.

Bioinspired computation methods, such as evolutionary algorithms and ant colony optimization, are being applied successfully to complex engineering and combinatorial optimization problems, and it is very important that we understand the computational complexity of these search heuristics. This is the first book to explain the most important results achieved in this area.

The authors show how runtime behavior can be analyzed in a rigorous way. in particular for combinatorial optimization. They present well-known problems such as minimum spanning trees, shortest paths, maximum matching, and covering and scheduling problems. Classical single-objective optimization is examined first. They then investigate the computational complexity of bioinspired computation applied to multiobjective variants of the considered combinatorial optimization problems, and in particular they show how multiobjective optimization can help to speed up bioinspired computation for single-objective optimization problems.

This book will be valuable for graduate and advanced undergraduate courses on bioinspired computation, as it offers clear assessments of the benefits and drawbacks of various methods. It offers a self-contained presentation, theoretical foundations of the techniques, a unified framework for analysis, and explanations of common proof techniques, so it can also be used as a reference for researchers in the areas of natural computing, optimization and computational complexity.