دسترسی نامحدود
برای کاربرانی که ثبت نام کرده اند
برای ارتباط با ما می توانید از طریق شماره موبایل زیر از طریق تماس و پیامک با ما در ارتباط باشید
در صورت عدم پاسخ گویی از طریق پیامک با پشتیبان در ارتباط باشید
برای کاربرانی که ثبت نام کرده اند
درصورت عدم همخوانی توضیحات با کتاب
از ساعت 7 صبح تا 10 شب
ویرایش:
نویسندگان: Éric D. Taillard
سری: Graduate Texts in Operations Research
ISBN (شابک) : 9783031137136, 9783031137143
ناشر: Springer
سال نشر: 2023
تعداد صفحات: [293]
زبان: English
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود)
حجم فایل: 15 Mb
در صورت تبدیل فایل کتاب Design of Heuristic Algorithms for Hard Optimization. With Python Codes for the Traveling Salesman Problem به فرمت های PDF، EPUB، AZW3، MOBI و یا DJVU می توانید به پشتیبان اطلاع دهید تا فایل مورد نظر را تبدیل نمایند.
توجه داشته باشید کتاب طراحی الگوریتم های اکتشافی برای بهینه سازی سخت. با کدهای پایتون برای مشکل فروشنده دوره گرد نسخه زبان اصلی می باشد و کتاب ترجمه شده به فارسی نمی باشد. وبسایت اینترنشنال لایبرری ارائه دهنده کتاب های زبان اصلی می باشد و هیچ گونه کتاب ترجمه شده یا نوشته شده به فارسی را ارائه نمی دهد.
این کتاب دسترسی باز تمام مراحل مورد نیاز برای طراحی الگوریتم های ابتکاری برای بهینه سازی دشوار را نشان می دهد. مشکل کلاسیک فروشنده دوره گرد به عنوان یک موضوع مشترک برای نشان دادن تمام تکنیک های مورد بحث استفاده می شود. این مشکل برای معرفی خوانندگان با موضوع ایده آل است زیرا بسیار شهودی است و راه حل های آن را می توان به صورت گرافیکی نشان داد. این کتاب دارای بسیاری از تصاویر است که به شما امکان می دهد مفاهیم را در یک نگاه درک کنید. این کتاب به فراابتکاری اصلی از زاویه ای جدید می پردازد و آن ها را به چند مفهوم کلیدی ارائه شده در فصل های جداگانه تجزیه می کند: ساخت، بهبود، تجزیه، تصادفی سازی و روش های یادگیری. سپس هر فراابتکاری می تواند به شکل ساده شده به عنوان ترکیبی از این مفاهیم ارائه شود. این رویکرد از ایجاد این تصور که فراابتکاری یک رشته غیر رسمی، نوعی مجسمه ابری است، اجتناب می کند. بعلاوه، کاربردهای ملموسی از مسئله فروشنده دوره گرد ارائه می دهد که تنها در چند خط کد نحوه طراحی یک اکتشافی جدید و حذف تمام ابهامات باقی مانده از یک چارچوب کلی را نشان می دهد. دو فصل به بررسی مبانی بهینه سازی ترکیبی و نظریه پیچیدگی کتاب را مستقل می کند. به این ترتیب، حتی خوانندگانی که سابقه بسیار محدودی در این زمینه دارند، می توانند تمام مطالب را دنبال کنند.
This open access book demonstrates all the steps required to design heuristic algorithms for difficult optimization. The classic problem of the travelling salesman is used as a common thread to illustrate all the techniques discussed. This problem is ideal for introducing readers to the subject because it is very intuitive and its solutions can be graphically represented. The book features a wealth of illustrations that allow the concepts to be understood at a glance. The book approaches the main metaheuristics from a new angle, deconstructing them into a few key concepts presented in separate chapters: construction, improvement, decomposition, randomization and learning methods. Each metaheuristic can then be presented in simplified form as a combination of these concepts. This approach avoids giving the impression that metaheuristics is a non-formal discipline, a kind of cloud sculpture. Moreover, it provides concrete applications of the travelling salesman problem, which illustrate in just a few lines of code how to design a new heuristic and remove all ambiguities left by a general framework. Two chapters reviewing the basics of combinatorial optimization and complexity theory make the book self-contained. As such, even readers with a very limited background in the field will be able to follow all the content.
Preface Heuristics and Metaheuristics Book Structure Source Codes for the Traveling Salesman Problem Exercises Acknowledgements Contents Part I Combinatorial Optimization, Complexity Theory, and Problem Modeling 1 Elements of Graphs and Complexity Theory 1.1 Combinatorial Optimization 1.1.1 Linear Programming 1.1.2 A Small Glossary on Graphs and Networks 1.1.2.1 Undirected Graph, Vertex, (Undirected) Edge 1.1.2.2 Directed Graph, Arcs 1.1.2.3 Incidence Matrix 1.1.2.4 Adjacency Matrix 1.1.2.5 Degree 1.1.2.6 Path, Simple Path, Elementary Path, and Cycle 1.1.2.7 Connected Graph 1.1.2.8 Tree, Subgraph, and Line Graph 1.1.2.9 Eulerian, Hamiltonian Graph 1.1.2.10 Complete, Bipartite Graphs, Clique, and Stable Set 1.1.2.11 Graph Coloring and Matching 1.1.2.12 Network 1.1.2.13 Flow 1.2 Elements of Complexity Theory 1.2.1 Algorithmic Complexity 1.2.2 Bachmann-Landau Notation 1.2.2.1 Definitions 1.2.3 Basic Complexity Classes 1.2.3.1 Encoding Scheme, Language, and Turing Machine 1.2.3.2 Class P of Languages 1.2.3.3 Class NP of Languages 1.2.3.4 Class NP-Complete 1.2.3.5 Strongly NP-Complete Class 1.2.4 Other Complexity Classes Problems References 2 A Short List of Combinatorial Optimization Problems 2.1 Optimal Trees 2.1.1 Minimum Spanning Tree 2.1.2 Steiner Tree 2.2 Optimal Paths 2.2.1 Shortest Path 2.2.1.1 Linear Programming Formulation of the Shortest Path 2.2.2 Elementary Shortest Path: Traveling Salesman 2.2.2.1 Integer Linear Programs for the TSP 2.2.3 Vehicle Routing 2.3 Scheduling 2.3.1 Permutation Flowshop Scheduling 2.3.2 Jobshop Scheduling 2.4 Flows in Networks 2.5 Assignment Problems 2.5.1 Linear Assignment 2.5.2 Generalized Assignment 2.5.3 Knapsack 2.5.4 Quadratic Assignment 2.6 Stable Set 2.7 Clustering 2.7.1 k-Medoids or p-Median 2.7.2 k-Means 2.8 Graph Coloring 2.8.1 Edge Coloring of a Bipartite Graph Problems References 3 Problem Modeling 3.1 Objective Function and Fitness Function 3.1.1 Lagrangian Relaxation 3.1.1.1 Lagrangian Relaxation for the Vertex Coloring Problem 3.1.1.2 Lagrangian Relaxation for the TSP 3.1.2 Hierarchical Objectives 3.2 Multi-Objective Optimization 3.2.1 Scalarizing 3.2.2 Sub-goals to Reach 3.3 Practical Applications Modeled as Classical Problems 3.3.1 Traveling Salesman Problem Applications 3.3.1.1 Minimizing Unproductive Moves in 3D Printing 3.3.1.2 Scheduling Coloring Workshop 3.3.2 Linear Assignment Modeled by Minimum Cost Flow 3.3.3 Map Labeling Modeled by Stable Set Problems Part II Basic Heuristic Techniques 4 Constructive Methods 4.1 Systematic Enumeration 4.1.1 Branch and Bound 4.1.1.1 Example of Implementation of a Branch and Bound 4.2 Random Construction 4.3 Greedy Construction 4.3.1 Greedy Heuristics for the TSP 4.3.1.1 Greedy on the Edges 4.3.1.2 Nearest Neighbor 4.3.1.3 Largest Regret 4.3.1.4 Cheapest Insertion 4.3.1.5 Farthest Insertion 4.3.2 Greedy Heuristic for Graph Coloring 4.4 Improvement of Greedy Procedures 4.4.1 Beam Search 4.4.2 Pilot Method Problems References 5 Local Search 5.1 Local Search Framework 5.1.1 First Improvement Heuristic 5.1.2 Best Improvement Heuristic 5.1.3 Local Optima 5.1.3.1 TSP 3-Opt 5.1.3.2 TSP Or-Opt 5.1.3.3 Data Structure for TSP 2-Opt 5.1.4 Neighborhood Properties 5.1.4.1 Connectivity 5.1.4.2 Low Diameter 5.1.4.3 Low Ruggedness 5.1.4.4 Small Size 5.1.4.5 Fast Evaluation 5.2 Neighborhood Limitation 5.2.1 Candidate List 5.2.1.1 Candidate List for the Euclidean TSP 5.2.1.2 TSP Neighborhood Limitation with 1-Trees 5.2.2 Granular Search 5.3 Neighborhood Extension 5.3.1 Filter and Fan 5.3.2 Ejection Chain 5.3.2.1 Lin-Kernighan Neighborhood 5.4 Using Several Neighborhoods or Models 5.5 Multi-Objective Local Search 5.5.1 Scalarizing 5.5.2 Pareto Local Search 5.5.3 Data Structures for Multi-Objective Optimization 5.5.3.1 Array 5.5.3.2 KD-Tree Problems References 6 Decomposition Methods 6.1 Consideration on the Problem Size 6.2 Recursive Algorithms 6.2.1 Master Theorem for Divide-and-Conquer 6.3 Low Complexity Constructive Methods 6.3.1 Proximity Graph Construction 6.3.2 Linearithmic Heuristic for the TSP 6.4 Local Search for Large Instances 6.4.1 Large Neighborhood Search 6.4.2 POPMUSIC 6.4.2.1 POPMUSIC for the TSP 6.4.3 Comments Problems References Part III Popular Metaheuristics 7 Randomized Methods 7.1 Simulated Annealing 7.2 Threshold Accepting 7.3 Great Deluge Algorithm 7.4 Demon Algorithm 7.5 Noising Methods 7.6 Late Acceptance Hill Climbing 7.7 Variable Neighborhood Search 7.8 GRASP Problems References 8 Construction Learning 8.1 Artificial Ants 8.1.1 Real Ant Behavior 8.1.2 Transcription of Ant Behavior to Optimization 8.1.3 MAX-MIN Ant System 8.1.4 Fast Ant System 8.2 Vocabulary Building Problems References 9 Local Search Learning 9.1 Taboo Search 9.1.1 Hash Table Memory 9.1.1.1 Hash Functions 9.1.2 Taboo Moves 9.1.2.1 Implementation of Taboo Status 9.1.2.2 Taboo Duration 9.1.2.3 Aspiration Criterion 9.2 Strategic Oscillations 9.2.1 Long-Term Memory 9.2.1.1 Forced Moves 9.2.1.2 Penalized Moves 9.2.1.3 Restarts Problems References 10 Population Management 10.1 Evolutionary Algorithms Framework 10.2 Genetic Algorithms 10.2.1 Selection for Reproduction 10.2.1.1 Rank-Based Selection 10.2.1.2 Proportional Selection 10.2.1.3 Natural Selection 10.2.1.4 Complete Selection 10.2.2 Crossover Operator 10.2.2.1 Uniform Crossover 10.2.2.2 Single-Point Crossover 10.2.2.3 Two-Point Crossover 10.2.2.4 OX Crossover 10.2.3 Mutation Operator 10.2.4 Selection for Survival 10.2.4.1 Generational Replacement 10.2.4.2 Evolutionary Strategy 10.2.4.3 Stationary Replacement 10.2.4.4 Elitist Replacement 10.3 Memetic Algorithms 10.4 Scatter Search 10.4.1 Illustration of Scatter Search for the Knapsack Problem 10.4.1.1 Initial Population 10.4.1.2 Creation of the Reference Set 10.4.1.3 Combining solutions 10.5 Bias Random Key Genetic Algorithm 10.6 Path Relinking 10.6.1 GRASP with Path Relinking 10.7 Fixed Set Search 10.8 Particle Swarm 10.8.1 Electromagnetic Method 10.8.2 Bestiary Problems References 11 Heuristics Design 11.1 Problem Modeling 11.1.1 Model Choice 11.1.2 Decomposition into a Series of Sub-problems 11.2 Algorithmic Construction 11.2.1 Data Slicing 11.2.2 Local Search Design 11.3 Heuristics Tuning 11.3.1 Instance Selection 11.3.2 Graphical Representation 11.3.3 Parameter and Option Tuning 11.3.4 Measure Criterion 11.3.4.1 Success Rate 11.3.4.2 Computational Time Measure 11.3.4.3 Solution Quality Measure Problems References 12 Codes 12.1 Random Numbers 12.2 TSP Utilities 12.3 TSP Lin and Kernighan Improvement Procedure 12.4 KD-Tree Insertion and Inspection 12.5 KD-Tree Delete 12.6 KD-Tree Update Pareto Set 12.7 TSP 2-Opt and 3-Opt Test Program 12.8 Multi-objective TSP Test Program 12.9 Fast Ant TSP Test Program 12.10 Taboo Search TSP Test Program 12.11 Memetic TSP Test Program 12.12 GRASP with Path Relinking TSP Test Program References Solutions to the Exercises Problems of Chap. 1 Problems of Chap. 2 Problems of Chap. 3 Problems of Chap. 4 Problems of Chap. 5 Problems of Chap. 6 Problems of Chap. 7 Problems of Chap. 8 Problems of Chap. 9 Problems of Chap. 10 Problems of Chap. 11 Reference Index