以多階層序的最佳化方法解有限制式的組合最佳化問題的研究(I)

Abstract

本計畫擬針對具有限制式及巨大解集(huge solution space)的組合最佳化問題 (constrained combinational optimization problem)提出一個多階層序的最佳化方法 (multi-level ordinal optimization)以便用較短的計算時間，求取一個不錯的(good enough)解。 本計畫將分成兩大部分。第一部分為理論部分，即針對有限制式的組合最佳 化問題提出多階層序的最佳化方法以及處理限制式的技巧。第二部分為應用部 分，我們將挑選兩類不同但卻深具代表性及重要性的有限制式的組合最佳化問 題，然後應用第一部分所提出的方法去求此兩類問題的不錯的解，並分析所求得 的解在整個巨大解集中排名的前百分比。 以多階層序的最佳化方法求解有限制式的組合最佳化的問題的關鍵在於(i) 如何處理限制式，(ii)每一階層的約化模式的提出及 (iii)設計如何根據所提出的 約化模式來挑取不錯的解的方法。最後我們將根據統計的方法以大量模擬的方式 來分析所求得的不錯的解在整個巨大解集中排名的前百分比。 限制式會因問題的不同而不同，而約化模式也會隨所考慮的組合最佳化問題 的特性而有所變化,所以在本計畫的應用部分中，我們亦將針對不同問題的需求 來研擬不同的處理限制式的方法，提出不同的約化模式以及挑選不錯的解的方 法。以下將就我們三年計畫的主要內容做一個概述: 第一年: (i) 針對具巨大解集的有限制式的組合最佳化問題，研究如何處理其限 制式。 (ii) 針對有限制式的組合最佳化問題，提出在多階層的最佳化方法中， 各階層的約化模式。 (iii) 設計根據多階層約化模式來挑選各階層的不錯的解的方法。 (iv) 提出多階層的序的最佳化方法的架構及演算法則。 (v) 提出以統計的方法來分析最後所求得的不錯的解在巨大解集中排 名的前百分比。 第二年: (i) Multiuser Orthogonal Frequency Division Multiplexing (OFDM)系統 的 Adaptive Subcarrier Assignment and Bit Allocation (ASABA)是一 個典型的有限制式組合最佳化問題，我們將針對此問題研擬一 個多階層序的最佳化方法來求解。此研擬將包括a. ASABA 問題的 限制式處理技巧。b. 各階層的約化模式，及c. 挑選各階層中不錯 的解的方法。 (ii) 以第一年所建立的分析方法來分析所求得的解在整個巨大解集中 的排名的前百分比，同時也將與現有的方法做比較。 第三年: (i) 針對網格計算系統(grid computing system)中的資源配置的最大可 靠度問題,研擬一個多階層序的最佳化方法以求得一個有不錯的可 靠度的資源配置。此研擬包括a. 網格計算系統資源配置的限制式 的處理， b. 各階層的約化模式，及c. 挑選各階層中不錯的解的 方法。 (ii) 將以第一年所建立的分析方法來分析所求得的解在整個巨大解集 中排名的前百分比，同時也將與現有的方法做比較。

In this project, we propose a multi-level ordinal optimization algorithm to solve constrained combinatorial optimization problems with huge solution space for a good enough solution using limited computation time. There are two parts in this project. The first part regards the theory. The second part is application. We will select two types of constrained combinatorial optimization problems and use the proposed algorithm to solve them. The keys of multi-level ordinal optimization are (i) how to handle the constraints,(ii) how to develop the approximate models in each level, and the design of methods to pick estimated good enough solutions from the candidate solution set in each level. At the end, we will use statistics based analysis to analyze the goodness of the good enough solution obtained by the multi-level ordinal optimization algorithm using extensive simulations. The constraints of combinatorial optimization problem may vary depending on the nature of considered problems. The same logic applies to the approximate model needed in each level. Therefore, in the application part of this project, we will provide different constraint handling technique, different approximate models and different methods for selecting estimated good enough solutions from the candidate solution set for different problems. The work of our three-year project can be outlined as follows: First year: (i) Study the constraint handling technique for constrained combinatorial optimization problem with huge solution space. (ii) Proposing approximate model in each level. (iii) Designing methods to select estimated good enough solutions. (iv) Proposing the multilevel ordinal optimization algorithm (v) Using statistics based analysis to analyze the goodness of the good enough solution obtained by the multi-level ordinal optimization algorithm using extensive simulations. Second year: (i) Proposing a multi-level ordinal optimization algorithm to solve the adaptive subcarrier assignment and bit allocation problem for multiuser OFDM system. The proposal includes: a. technique for handling constraints b. approximate models in each level, and c. method to pick good enough solutions in each level. (ii) Use the statistics based analysis to analyze the goodness of the obtained good enough solution. Third year: (i) Proposing a multi-level ordinal optimization algorithm to solve the resource allocation problem in grid computing system for maximizing the reliability. The proposal includes: a. technique for handling the constraints in grid computing system, b. approximate models in each level, and c. method to pick good enough solutions in each level. (ii) Use the statistics based analysis to analyze the goodness of the obtained good enough solution.