2-3-5. Optimization

2-3-5.　最適化

2-3-5-1. Objective functions (purpose)

Consider the mathematical programming question, where f: A→R. The goal is to find X0 that satisfies the following equation, 

2-3-5-1. 目的関数（計算目標）

　f:A→Rとした場合の数理計画問題を考える。目標は以下の式を満たすX0を見つけることである。

     In this example, “f” is called the objective function to be minimized over variable “x” and condition "A". Generally, in optimization design, designed objects are decided by defining constraint conditions. In the design simulation process, objective functions are used to determine constraints and the minimal solution if it is in a linear programming question. 

　この例では、変数「x」と条件「A」に対して、最小化すべき目的関数を「f」と呼んでいる。一般に最適化設計では、制約条件を定義することで設計対象を決定する。設計のシミュレーションでは、線形計画問題であれば、制約条件を決定し、最小解を決定する手法として目的関数が使われる。 

     In the Traveling Salesman Problem(TSP), for example, the objective function is described as "Dij" with the distance between the number of nodes (N) and whether or not to include its arc (the aisles of nodes). Xij= 1 means the arc is included in the circuit, while Xij= 0 means the arc is not included. The fitness value of the circuit F is described as,

　例えば、巡回セールスマン問題(TSP)では、目的関数はノードの数（N）とそのアーク（ノードの通路）を含めるかどうかの距離で「Dij」と記述される。「Xij=1 」はそのアークが順路に含まれることを意味し、「Xij=0 」はそのアークが含まれないことを意味する。回路Fの適応度値は次のように記述される。 

     A reverse process is used for analysis. The levels of objectives are calculated, and variables are found from the plural objectives. Following this, the objectives are used in the process going from design to analysis.

　分析には逆のプロセスを用いる。目的のレベルを計算し、複数の目的（関数）から変数を求める。このようにして、設計から解析までのプロセスでその目的（関数）が使われる。 

2-3-5-2. GA vs others

When looking for the optimal parameters (design variables) for an objective function whether,r from calculation results or experimental results using the parameter(s), the various parameters need to be tested to find out which conditions improve results. The search needs to be conducted efficiently, not by randomly analyzing possibilities but by properly using combinatorial optimization methods.

2-3-5-2.遺伝的アルゴリズムとその他アルゴリズムの比較

　目的関数に最適なパラメータ（設計変数）を計算結果やパラメータを用いた実験結果から求める場合、様々なパラメータを検証し、どのような条件で結果が改善されるかを調べる必要がある。その際、無作為に可能性を分析するのではなく、組合せ最適化手法を適切に用いて、効率的に探索する必要がある。

     There are various combination optimization methods, such as Simulated Annealing, Genetic
Algorithm, Tabu Search, Simulated Evolution, and Stochastic Evolution.
Compared to the other methods, GA has several advantages.

1. GA can adapt to the evaluation function without referring to the differentiation possibilities of the objective function.

2. It can directly operate by devising solution expressions.

3. A solution can be treated as a perfect solution candidate during the early stages of the search, even if it has not been developed through the procedure.

4. It is easy to extend to multiple-purpose questions because GA searches by using multipoint.

     GA works effectively on questions where objective function calculations have problematic qualities. Other algorithms are necessary to solve questions which have a gradual-sloping solution space with robust characteristics.

　世には様々な組み合わせ最適化手法がある、例としてシミュレーション アニーリング、遺伝的アルゴリズム、タブ探索、シミュレーション進化計算、そして確率的進化などである。これらの他の方法と比較して、GAには下記のようないくつかの利点がある。

1. 目的関数の微分可能性を参照せずに評価関数に適応できる。

2. 解答式を工夫すれば直接操作することができる。

3. 探索の初期段階で、手順を踏んでいない解でも完全解候補として扱うことができる。

4. GAは多点を用いて探索するため、多目的問題への拡張が容易である。

　GAは、目的関数の計算が不確かな性質を持つ問題に有効に働く。ロバストな性質を持つ緩やかなスロープによる解空間の問題を解くためには、他のアルゴリズムが必要である。

2-3-5-3. Simulated Annealing

Simulated Annealing (SA) is one of the most widely used methods to solve optimal combination questions. SA is a heuristic program with general-purpose adaptability, belonging to a class of non-deterministic algorithms. In an SA procedure, “T” is the calculation period and is determined beforehand. The system repeats its code until the time is equal to “T”. The following, in brief, describes how the coding progresses.

2-3-5-3.  焼きなまし法（シミュレーテッド・アニーリング）

　シミュレーテッドアニーリング(SA)は、最適な組み合わせの問題を解くために、最も広く用いられている手法の一つである。SAは汎用的な適応性を持つ発見的（ヒューリスティック）プログラムであり、非決定論的 アルゴリズムのクラスに属する。SA手順において、"T "は計算の期間であり、あらかじめ決定される。システムは、時間が "T "に等しくなるまで、そのコードを繰り返す。以下、簡単にコード化がどのように進行するかを説明する。

A suitable state (solution) is chosen with a specific score.

If the score of the next state is better than the current score, the next state is selected.

If the score of the next state is worse than the score of the current state, it moves on to the next state if Time “t” is close to 0. It does not move on if it is the final stage when “t” is close to “T”.

In the end, the state which is related to the best score is chosen.

Example: If it is a question of calculating the [maximum of y=f(x)],

The state is “x”

The following state is [x' = x+a (where ‘a’ is an incrementally small value) ]

The score is “y”

This would be continued for a period of time “T”.

特定のスコアで適切な状態（解）を選択する。

次の状態のスコアが現在のスコアよりも良ければ、次の状態が選択される。

次の状態のスコアが現在の状態のスコアよりも悪ければ、時間 "t "が0に近ければ次の状態に移動し、時間 "t "が "T "に近ければ最終段階には移動しない。

最終的には、ベストスコアに関係する状態が選択される。

例：［yの最大値=f(x)］を計算する問題であれば

状態は’X’。

次の状態は、[x' = x+a (ここで、'a'は増分的に小さい値) ]。

スコアは "y"

これは、時間 "T "の間、継続されることになる。

2-3-5-4. Dantzig’s Simplex Method

The Simplex method is used when maximizing or minimizing a purpose function in linear programming. The purpose function seeks the intersection point of the limiting conditions. Therefore, a solution can be obtained on all intersection points generated by a limiting condition if the objective function is investigated at each intersection. The method which was made to investigate an intersection efficiently is called the “Simplex Method”. Its computational procedure is

1. Find a feasible base solution by some method.

2. Investigate whether the obtained solution is the optimal solution.

3. If a solution is optimal, the procedure ends. Otherwise, use the new, improved solution and return to step 2.

2-3-5-4.　ダンツィーグのシンプレックス法

　シンプレックス法は線形計画（プログラミング）で目的関数を最大化または最小化するときに使用される。目的関数は制限された条件の交点を求める。したがって、制限された条件で造られたすべての交点について、目的関数の交点を調査すれば解を得ることができる。

　交点を効率的に調査するために作られた方法を「シンプレックス法"」という。その計算手順は

1. 何らかの方法で基本的な実行可能な解を見つける。

2. 得られた解が最適解であるかどうかを調べる。

3.  解が最適であれば、その手順を終了する。そうでなければ，新しい改良された解を用いて，ステップ2に戻る．

2-3-5-5. Stochastic Diffusion Search / Ant Algorithms

Both “Stochastic diffusion search"(SDS) and "ant algorithms" are part of the “group intelligence" algorithms used in artificial intelligence systems. They are based on the study of the collective behaviour of a self-organising system.

     SDS is a probabilistic wide area search based on agents and an optimization method. The method is suitable for problems which can be decomposed. Each agent repeats evaluating hypotheses by randomly choosing a partial purpose function set by a parameter linked to the current hypotheses. In the standard SDS, the evaluation result of the partial function has only 2 states; each agent is either activated or deactivated. The information about the hypothesis is spread to a group of individuals by using communication between agents. In contrast, “Stigmergy'', an SDS used to model the optimisation of ant colonies, learnt from ants' queuing behaviour. Hypotheses are transmitted via one-to-one communication between agents. A regular feedback system gradually establishes groups of individual agents around a wide area. SDS is an effective, mathematically describable search algorithm.

2-3-5-5. 確率拡散探索　/　アントアルゴリズム

　確率拡散探索(SDS)」と「アントアルゴリズム」は、いずれも人工知能システムで用いられる「群知能」アルゴリズムの一部である。これらは、自己組織化システムの集団行動（群行動）の研究に基づいている。

　SDSはエージェントに基づく確率的な広域探索であり、最適化手法でもある。この方法は、分解可能な問題に適している。各エージェントは、現在の仮説に関連するパラメータで設定された部分目的関数をランダムに選択し、仮説の評価を繰り返す。標準的な SDS では、部分関数の評価結果は、各エージェントが活性化されるか非活性化されるかの 2 状態のみである。また、仮説に関する情報は、エージェント間のコミニケーションを利用して集団に広まる。一方、アリコロニーの最適化をモデル化したSDS「スティグマジー」は、アリの行列行動からからヒントを得て方法化したものである。解の仮説は、エージェント間の1対1のコミュニケーションによって伝達される。定期的なフィードバックシステムにより、個々のエージェントのグループが徐々に広い範囲に形成されていく。SDSは、数学的に記述可能な効果的な探索アルゴリズムである。

     Ant colony optimization (ACO) is a meta-heuristic optimized algorithm which is used to search for approximate solutions to difficult combination optimization problems. ACO attempts to find a solution with an artificial ant that imitates a real ant, moving over graphs of issues. Artificial ants help other artificial ants to search for a better solution by leaving artificial pheromones on a graph. ACO has shown its usefulness in solving a large number of optimization problems. 

　アントコロニー最適化（ACO）は、難しい組み合わせの最適化問題の近似解を探索するために使われるメタヒューリスティック最適化アルゴリズムである。ACOは、本物のアリを模した人工アリが、問題のグラフ上を移動しながら解を求めようとするものである。人工アリは、人工フェロモンをグラフ上に残すことで、他の人工アリがより良い解を探索するのを助ける。ACOは、多くの最適化問題の解決に有用であることが示されている。 

2-3-6. Evolutionary Computing

'Evolutionary Computing' is a method to optimize, search, and learn from the analogy of the evolution of creatures in nature. Creatures on the earth have taken billion of years to evolve gradually. Applying that evolutionary methodology to engineering is the fundamental point of ‘Evolutionary Computing. The calculation methodology of 'Evolutionary Computing' follows the steps below.

2-3-6. 進化的計算

　「進化的計算（コンピューティング）」とは、自然界の生物の進化を模して、最適化、探索、学習を行う手法である。地球上の生物は何十億年もかけて少しずつ進化してきた。その進化の方法論を工学に応用することが「進化的計算」の根幹である。その計算方法は、以下のようなステップを踏む。 

     First of all, as a problem is identified, possible solutions are presented as virtual creatures (or sets of genetic factors). The manner of expressing this has several variations. Then, groups of individuals are constructed by generating various selections of possible solutions (virtual creatures based on various sets of genetic factors). 

　まず、問題が特定されると、可能な解決策が仮想の生き物（あるいは遺伝子の集合）として提示される。その表現方法にはいくつかのバリエーションがある。そして、様々な解の選択（様々な遺伝的要因の集合に基づく仮想的生物）を生成して、個体群を構築する。 

     Then, the evaluating function assesses each individual in the group. These assess the level of suitability of the individual in addressing the identified problem. Based on the assessments, the dominant individuals are kept in the group and duplicated; the recessive individuals are deleted. Next, a genetic cross-over or mutative methodology similar to gene recombination is applied to individuals in the groups. This leads to a new repetition of valuation, selection, and gene recombination steps. This is the basic flow of 'Evolutionary Computing. 

　そして評価関数では、グループ内の各個体を評価する。これは、特定された問題に対処するために、その個体がどの程度適しているかを評価するものである。評価結果に基づいて、優勢な個体はグループ内に残して複製し、劣勢な個体は削除する。次に、グループ内の個体に対して、遺伝子組み換えに似た遺伝子交叉や突然変異の手法が適用される。これによって、評価、選択、遺伝子組換えというステップが新たに繰り返される。これが「進化型コンピューティング」の基本的な流れである。 

Evolutionary computing includes several variations:

- Genetic Algorithm; GA

- Genetic Programming; GP

- Evolution Strategy; ES

- Evolutionary Programming; EP

- Classifier System; CS

Although those are commonly based on the evolution of creatures, there are various differences in the method of the modelling, or in the processing procedures.

「進化的計算」にはいくつかのバリエーションがある。

- 遺伝的アルゴリズム; GA

- 遺伝的プログラミング; GP

- 進化戦略; ES

- 進化的プログラミング; EP

- 分類システム; CS

これらは共通して生物の進化をベースにしているが、モデル化の方法や処理の手順には様々な違いがある。