Якупов Илья Юрьевич Эффективные алгоритмы инкрементальной и асинхронной недоминирующей сортировки для многокритериальных эволюционных алгоритмов

Краткое описание

Якупов Илья Юрьевич Эффективные алгоритмы инкрементальной и асинхронной недоминирующей сортировки для многокритериальных эволюционных алгоритмов
ОГЛАВЛЕНИЕ ДИССЕРТАЦИИ
кандидат наук Якупов Илья Юрьевич
Реферат

Synopsis

Introduction

Chapter 1. Analytical Overview and Motivation

1.1 Mathematical Optimization

1.1.1 Problem Overview

1.1.2 Approaches for Multiobjective Optimization Problems

1.2 Notation and Basic Definitions

1.3 Generational Multiobjective Optimization Algorithms

1.3.1 Aggregation-Based Algorithms

1.3.2 Criterion-Based Algorithms

1.3.3 Dominance-Based Algorithms

1.3.4 Hybrid Algorithms

1.3.5 The NSGA-II Algorithm

1.4 Steady-state evolutionary multiobjective optimization algorithms

1.4.1 Incremental Non-Dominated Sorting

1.4.2 Efficient Non-domination Level Update

1.5 Chapter 1 Conclusion

Chapter 2. Two-Dimensional Incremental Non-Dominated Sorting

2.1 Used Data Structures

2.2 Algorithm Description

2.2.1 Data Structure

2.2.2 Lookup

2.2.3 Insertion

2.2.4 Deletion of the Worst Solution

2.2.5 Querying the Л-th Solution

2.3 Experiments

2.3.1 Synthetic Tests

2.3.2 Tests as a Part of NSGA-II

2.3.3 Scalability

2.4 Chapter 2 Conclusion

Chapter 3. Incremental Non-Dominated Sorting for Arbitrary Dimensions

3.1 Preliminaries

3.1.1 Definitions

3.1.2 The Divide-and-Conquer Approach

3.2 Adapting the Divide-and-Conquer Algorithm to Incremental Sorting

3.2.1 Finding the Rank of the New Point

3.2.2 Reducing the Set of Points to Work With

3.2.3 Taking Advantage of Known Ranks

3.2.4 Is-Anything-Changed Heuristic

3.2.5 Putting Everything Together

3.3 Experiments

3.4 Chapter 3 Conclusion

Chapter 4. Algorithms for Asynchronous Non-Dominated Sorting

4.1 Concurrency Primitives

4.2 Introducing Concurrency

4.2.1 The Compare-And-Set Approach

4.2.2 A Time-Stamping Modification

4.2.3 The Approach with Finer-Grained Locks

4.2.4 Recomputation of the Crowding Distance

4.3 Experiments

4.3.1 Asynchronous NSGA-II: Details and Parameters

4.3.2 Experiments with Fixed Number of Threads

4.3.3 Results and Discussion: Running Times

4.3.4 Results and Discussion: Hypervolumes

4.3.5 Exploring Scalability When Adding Worker Threads

4.3.6 Performance under Heavy CPU Load

4.4 Chapter 4 Conclusion

Conclusion

References

List of Figures

List of Tables

Appendix A. Copies of Author's Publications

Реферат