多階層序的最佳化方法---效能分析與應用

Abstract

本計畫擬針對具有巨大解集(huge solution space)的困難最佳化問題(hard optimization problem)提出一個多階層序的最佳化方法(multi-level ordinal optimization)以便用較短的計算時間，求取一個不錯的(good enough)的解。 本計畫將分成兩大部分。第一部分為理論部分，即多階層序的最佳化方法的 提出及如何分析其效能(performance)。第二部分為應用部分，我們將挑選兩類 不同但卻深具代表性的困難最佳化問題，然後應用第一部分所提出的方法去求此 兩類問題的不錯的解，並分析所求得的解在整個巨大解集中排名的前百分比。 多階層序的最佳化方法的關鍵在於(i)每一階層的約化模式的提出以及如何 建立約化模式與真正模式之間的誤差分佈的機率模式(ii)設計如何根據所提出 的約化模式來挑取不錯的解的方法。多階層序的最佳化方法的效能分析除了與上 述之(i)及(ii)有關外，也與所考慮的困難最佳化問題的Order Performance Curve(OPC)的分佈有關。所以我們也必須建立一套分析所考慮問題的OPC 的分佈 的方法，然後才能根據有代表性的OPC 配以所建立誤差分佈的機率模式以大量模 擬的方法來分析所求得的不錯的解究竟在整個巨大解集中排名的前百分比。 約化模式可以有很多種,應隨所考慮困難最佳化問題的特性而有所變化,所 以在本計畫的應用部分中，我們亦將針對不同問題的需求來研擬不同的約化模式 以及不同的挑選不錯的解的方法。所以我們的三年計畫,其主要內容可述之如下: 第一年: (i)提出多階層的最佳化方法的架構及演算法則。 (ii)提出約化模式及分析其與真正模式之間的誤差分佈的機率模式的 方法。 (iii)提出建立所考慮問題在各種可能狀況下的OPC 分佈的方法。 (iv)設計根據約化模式挑選不錯的解的方法 (v)根據約化模式、有代表性的OPC 及所設計的挑選不錯的解的方法， 提出以大量模擬的方法來分析最後所求得的不錯的解在巨大解集 中排名的前百分比。 第二年: (i)針對G/G/1/K polling system,研擬一個多階層序的最佳化方法以 求得一個不錯的number limited service discipline 來minimize customer 在queue 中的average(expected) waiting time。 (ii)將以第一年所建立的分析方法來分析所求得的解在整個巨大解集 中排名的前百分比。 第三年: (i)針對Multiuser Orthogonal Frequency Division Multiplexing (OFDM)系統研擬一個多階層序的最佳化方法以求得一個不錯的 subcarrier 及 bit 的allocation 以便minimize power consumption。 (ii)以第一年所建立的分析方法來分析所求得的解在整個巨大解集中 的排名的前百分比。