Programmable Architecture

-Towards Human Interactive, Cybernetic Architecture-

Kensuke Hotta (B.Eng, M.Eng, Msc)
Architectural Association School of Architecture, 2013

プログラマブル アーキテクチャ


堀田憲祐, 英国建築協会建築学校 

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. 目的関数(計算目標)


     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. 


     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.



     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は多点を用いて探索するため、多目的問題への拡張が容易である。


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 "に近ければ最終段階には移動しない。




次の状態は、[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 では、部分関数の評価結果は、各エージェントが活性化されるか非活性化されるかの 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. 


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