The Resource Allocation problem is any problem that can be defined as the division of a "Resource" among a large number of "Consumers". The "Consumers", in this case, are parameters of an function optimization problem. Two examples of Real World Resource Allocation problems are the Financial Portfolio Optimization, and the Economic Load Dispatch problems.

In the Financial Portfolio Optimization the "Resource" is the Financial Capital, and the "Consumers" are the different assets and securities that a trader can invest using this capital. A trader wants to form a Portfolio with many different assets in order to reduce the risk, i.e., the chance that the value of the portfolio will change suddenly. A well chosen portfolio will have a very low risk with a reasonable return, and is important for long term financial investments such as retirement funds, insurances, etc. Thus, the Financial Portfolio Optimization problem has great relevance in the Financial Engineering Field.

In the Economic Load Dispatch problem, the "Resource" is the total energy demand of a Power Supply System, and the "Consumers" are the Energy Generators in this system. Each Generator has a minimum and a maximum output, and different levels of fuel consumption for different output levels. By distributing the energy demand correctly among the generators, the whole system will not only consume less fuel, but also work more reliably and with a smaller environmental impact.

In this work, we develop a hybrid optimization system specialized in solving Resource Allocation problems, called the MEMETIC TREE-BASED GENETIC ALGORITHM (MTGA). The MTGA is based on evolutionary algorithms (EA), and uses some novel improvements to the EA framework. EAs are population-based optimization heuristics inspired in the natural evolutionary process. These Evolutionary Algorithms have been shown to be successful in hard and high dimensional problems. We develop three new techniques that together greatly improve the performance of EAs in the Resource Allocation domain: a specialized problem representation, a local search operator, and a topological global search framework.

The first new technique is the specialized problem representation. The traditional way to represent a problem's solution in an evolutionary algorithm (referred to as a "Genome") is to use an array where each element in the array is one parameter of the solution. However, in many Resource allocation problems, specially those with a high degree of epistasis, it is also very important to know how different parameters are related to each other. Our new representation, called the tree-based representation, is composed by a binary tree, where the terminal nodes are the parameters of the problem, and the intermediate nodes are local weights that determine how the resource is divided among the parameters. Using this representation, it is possible to create a hierarchical relationship tree between the parameters, which gives us parameter relationship information, which can be used to solve a given problem more efficiently.

The second new technique is the local search optimization operator. It is well known that in real valued problem domains, the use of a local search optimization operator greatly improves he performance of Evolutionary Algorithms. This hybridization is usually called "Memetic Algorithms" (MA). However, the implementation of the search optimization operator is not always straightforward, depending on the problem domain. On highly dimensional problems, trying to locally optimize all the dimensions at the same time may be too costly. We have developed a local search optimization which uses the tree-structure described previously to effect a divide-and-conquer policy which allows the operator to locally optimize small parts of the solution at a time, in a much simpler and faster fashion. In our local search operator, a tree representation is divided into sub trees, and each sub-tree, from the bottom to the top, is optimized individually before being re-inserted into the original solution. In this way, we avoid trying to solve a high-dimensional optimization problem and replace it with many low-dimensional problems.

The third and last new technique studied in this work to for the MTGA optimization system is the Topological Framework. In very hard optimization problems, even Evolutionary Algorithm can display sub-optimal results. This happens mainly when a problem has too many deceptive local optima, and the algorithm can not consistently find the global optima. A way to avoid having an EA getting stuck into a local optima is to promote its "Diversification". Diversification means different procedures to guarantee that the solutions in the population explore a wide area in the search space. The diversification procedure we study here is the Topological Strategy (TS). In the TS we distribute the solutions of a EA in a grid, and we only allow recombination between solutions which are in the same cell in the grid. At every iteration of the algorithm, each solution has a chance of moving to a neighbor cell. This movement creates a dynamic where the best solutions form "islands", which aggregate other solutions around them. Each island is then able to explore a different area of the search space, reducing the chance that the system as a whole will be trapped in a local optima.

In order to analyze the above MTGA system, we perform three sets of experiments.

The first set is in the Portfolio Optimization problem Domain. We execute a simulation using historical price data from the NASDAQ and the S&P 500 datasets, in order to evaluate the portfolios generated by the MTGA and compare them with a state of art evolutionary optimization system (differential evolution) and a traditional financial benchmark. We simulate 72 different scenarios between 2006 and 2008. The results in these experiments tells us that the MTGA is able to outperform the other comparative techniques, and has proved itself to be an effective system for the optimization of financial portfolios. A deeper analysis of the results show that the MTGA is able to both select the best assets to compose the portfolio and to optimize their relative weights at the same time, while previous methods are only able to perform one or the other. Also, the tree representation introduced in this work was able to learn the structure of the problems, and the best individuals generated were those which featured structures that included problem domain knowledge.

The second set of experiments involved mathematical functions which are often used to benchmark parameter optimization problems. Our objective was to access whether the MTGA has the ability to solve problems other than the financial Portfolio Optimization problem. Our tests included problems with 20 and 200 dimensions, of varying difficulty. In the results, the MTGA showed a very high degree of reliability with regards to the dimensionality of the problem. While in the cases with lower dimensions all the methods performed comparably, the MTGA showed a reduced loss in performance for higher dimensions when compared to the other methods.

In the third set of experiments, we apply the MTGA to a set of problems from the Economic Load Dispatch domain. There problems include benchmarks from some seminal works in this problem. The results in this experiment highlight the the abilities and limitations of the MTGA system, and allow us to outline the problem domains in which the MTGA is able to excel.

In the end, we developed a system which shows a significant superior performance in the Portfolio Optimization domain by applying the principle of including domain knowledge to the problem representation. This principle shows that the evolution paradigm for optimization problems is much stronger than previously though, and is able to learn extra information about a problem domain, as long as the representation allows for such information to be stored in it. Our system provides a distinct service in this real world application, and indicates the ability to be useful in other resource allocation problems.

本論文は「Development of Hybrid Evolutionary Techniques to Solve Resource Allocation Problems(資源配分最適化問題への進化論的アプローチ)」と題し,9章からなり,資源配分問題の効率的な解法のために木構造遺伝型,局所探索法,およびセル戦略を統合したハイブリッド進化計算手法を提案し,実際的な問題における最適化実験を通して提案手法の有用性を検証している.

第1章は序論であり,主題と進化計算について述べている.また従来手法の持つ問題点について議論している.

第2章では,資源配分最適化問題について述べ,この問題を従来手法で解く際の困難性について議論している.資源配分最適化問題は,パラメーターの合計が資源量に等しいという制約下での最適化問題である.その結果,各パラメータの最適な値は他のパラメータの値に強く依存し(Epstasisと呼ばれている),従来手法で効率的に解くことは難しい.さらに本章では,金融ポートフォリオ問題やELD(Economic Load Dispatch, 経済的負荷分担)などの資源配分問題の実世界における例について説明している.

第3章では,金融ポートフォリオ最適化問題の詳細について述べる.金融ポートフォリオでは,複数の銘柄の重みをバランスして,リスクを下げることを目的とする.金融会社が長期間の投資を行うためには,リスクの低いポートフォリオを作成する必要があるため配分の最適化は金融工学における重要な問題である.しかしながら,ポートフォリオで使用する銘柄の数は非常に多く,第2章で述べたEpstasisも存在するため,効率的に解くのは極めて難しい問題の1つである.

第4章では,TGAとよばれる進化計算におけるあらたな遺伝子表現を提案する.TGAは問題の解候補を表現するための木構造による遺伝子表現である.木構造を用いることにより,進化計算アルゴリズムは最適化を行うパラメータ間の関係を効果的に学習することができ,資源配分問題においては従来手法より効率よく解を探索できる.性能向上(どれぐらいパラメータ間の関係情報を学習できるか)については,シミュレーション実験結果を行い確認している.さらに,ポートフォリオ最適化問題に対する実験を行い,従来手法に比べてより最適で簡潔な解が得られることを示している.

第5章では,TGAシステムに局所探索を導入する.遺伝的アルゴリズムと局所探索を統合したハイブリッドアルゴリズムは「メメティックアルゴリズム(Memetic Algorithm)」と呼ばれており,実数値問題に対して有効であることが知られている.本提案手法において,Memetic AlgorithmはTGA内の木構造内の重みを最適化するために使用される.問題の自由度が高い場合,Memetic Algorithmの計算量は非常に多くなるが,分割統治法により独立して部分木を最適することが可能である.ポートフォリオ最適化問題に対する実験により,Memetic Algorithmの有効性を定量的に示している.

第6章では,TGAシステムにセル戦略を加える手法を提案する.遺伝的アルゴリズムのセル戦略では,集団をグリッドに分割し,各セルに一つの個体を入れる.これにより,集団中の交叉を限定することができ,局所解に陥ってしまう危険性を低減させることができる.さらに,セル戦略はシステムパラメータの自動調整を可能にする.本章では4種類のセル戦略について比較実験を行っている.実験結果から得られた最良の組み合わせを以下で構築する最適化システムに採用する.

第7章では,4~6章で示された手法に基づくTGAシステムを3種類の問題(数学的なベンチマーク最適化問題,金融ポートフォリオ最適化問題およびELD最適化問題)に対して適用し,検証実験を行う.実験により,従来手法と比較して効率が向上することを定量的に確認している.

第8章では,提案したハイブリッド進化計算手法(遺伝子表現,セル戦略および局所探索)のメリットについて議論する.とくに,実世界問題を効率よく解くために,問題空間が有する特殊な情報構造を遺伝子構造で表現するための方法について議論する.

第9章においては,本論文のまとめと今後の展望が述べられている.

以上これを要するに本論文は,資源配分の最適化問題を解くためのハイブリッド進化計算手法を提案し,複数の実際的な問題に適用して有用性を実験的に検証したものであり,情報学の基盤の発展に貢献するところが少なくない.したがって,博士(科学)の学位を授与できると認める.