JPH06348684A

JPH06348684A - 組合せ最適化装置

Info

Publication number: JPH06348684A
Application number: JP13715993A
Authority: JP
Inventors: Ryuichi Mato; 藤隆一間; Hitoshi Araki; 木均荒; Hitoshi Kato; 藤等加; Shinji Nojima; 島晋二野
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1993-06-08
Filing date: 1993-06-08
Publication date: 1994-12-22
Anticipated expiration: 2015-10-03
Also published as: JP3095313B2

Abstract

(57)【要約】【目的】各種の組合せ最適化問題を視覚的に定義する
部分と共通に使用できる最適化手段とを分離し、使用者
が難解な最適化手段を知らなくても容易に、組合せ最適
化を処理できるようにする。【構成】組合せ単位が移動する平面である移動平面の
形状と移動平面上の名称を視覚的に定義する手段１０１
と、移動平面上を移動する組合せ単位の形状と組合せ単
位上の点の名称を視覚的に定義する手段１０２と、移動
平面上を組合せ単位が移動できる種類を定義する手段１
０３と、組合せ移動単位の位置に対応して組合せの良し
悪しの尺度であるコストを定義する手段１０４と、上記
各手段により定義された情報に基づき、コストが極大ま
たは極小となる移動平面上の組合せ単位の最適な配置と
最適な組合せを求める手段１０５とを備えている。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、組合せ最適化分野にお
ける組合せ最適化問題を解法する組合せ最適化装置に関
するものである。

【０００２】

【従来の技術】近年、組合せ最適化装置は、スケジュー
リング、レイアウトなどの組合せ最適化分野で盛んに利
用されるようになってきた。

【０００３】この組合せ最適化装置は、例えば、S. Kir
kpatrick, and V. A. Norton andM. P. Vecchi. "Optim
ization by Simulated Annealing" (Science, Vol. 22
0,pp671-680, May 1983)に記載されているシミューレー
ティッド・アニーリングや山登り法などの最適化方法に
よる構成が知られている。

【０００４】以下、図１２を参照しながらスケジュール
問題を対象として、従来の組合せ最適化装置について説
明する。このスケジュール問題は、各仕事の順序関係な
どの制約条件を考慮して、最短時間で終了する仕事のス
ケジュールを決定する問題である。以下の簡単なスケジ
ュール問題を例として説明する。問題・１日の作業時間は、２０時間である。・仕事１は、４時間の作業時間を必要とする。・仕事２は、３時間の作業時間を必要とする。・仕事３は、３時間の作業時間を必要とする。・仕事４は、５時間の作業時間を必要とする。・仕事３は、仕事１が終了した後に実行する。・仕事２は、仕事３が終了した後に実行する。・仕事４は、仕事２が終了した２時間後に実行する。

【０００５】図１２において、１２０１は組合せ単位が
移動する平面の形状と移動平面上の点の名称を定義する
移動平面定義手段、１２０２は移動平面の形状を移動す
る組合せ単位の形状と組合せ単位上の点の名称を定義す
る組合せ単位定義手段、１２０３は移動平面上を組合せ
単位が移動できる種類を指定する移動種類定義手段、１
２０４は移動平面の組合せ移動単位の位置により組合せ
の善し悪しの尺度であるコストを定義するコスト定義手
段、１２０５はこれら各定義手段により定義された情報
に基づき、組合せ単位移動平面上の組合せ単位の最適な
配置と最適な組合せを求める最適化手段である。

【０００６】以下、図１２を参照して従来の組合せ最適
化装置の動作について説明する。なお、ここでは、装置
の説明に主眼を置いており、効率は考慮していないこと
を前提とする。まず移動平面定義手段１２０１は、移動
平面の形状と平面上の点の名称を定義する。移動平面と
しては、１日の作業時間が２０時間であり、４種類の仕
事があるので、４行２０列の移動平面を定義する。具体
的には、４行２０列の配列などのデータ構造とする。こ
の問題においては、移動平面上に点の名称を定義する必
要はない。

【０００７】次に組合せ単位の形状を定義する。仕事
１、仕事２、仕事３と仕事４は、それぞれ４時間、３時
間、３時間と５時間の作業時間を必要とするので、各仕
事を組合せ単位として、各形状は、１行４列、１行３
列、１行３列と１行５列の形状と定義する。次に組合せ
単位上の点を定義する。この点はコスト定義手段１２０
４で使用される。仕事１の１行４列の点を”仕事１の
右”、仕事２の１行１列の点を”仕事２の左”、１行３
列の点を”仕事２の右”、仕事３の１行１列の点を”仕
事３の左”、１行３列の点を”仕事３の右”、仕事４の
１行１列の点を”仕事３の左”と定義する。

【０００８】次に移動種類定義手段１２０３は、各移動
単位の初期位置と移動の種類を定義する。仕事１は、移
動平面の１行の位置を左右に移動でき、仕事２は、移動
平面の２行の位置を左右に移動でき、仕事３は、移動平
面の３行の位置を左右に移動でき、仕事４は、移動平面
の４行の位置を左右に移動できるように定義する。

【０００９】次にコスト定義手段１２０４は、組合せ単
位の位置に対応して、コストの計算方法を定義する。仕
事３は、仕事１が終了した後に実行しなければならない
ので、”仕事３の左”は、”仕事１の右”より移動平面
上で左列か同列にあれば、５０点コストに加算する。仕
事２は、仕事３が終了した後に実行しなければならない
ので、”仕事２の左”は、”仕事３の右”より移動平面
上で左列か同列にあれば、５０点コストに加算する。仕
事４は、仕事２が終了した２時間後に実行しなければな
らないので、”仕事４の左”は、”仕事２の右”に２加
算した列より移動平面上で左列か同列にあれば、５０点
コストに加算する。

【００１０】ここでは、コストが低い程、最適な配置と
なり、コストが０であれば、制約条件を満たしたスケジ
ューリングとなる。

【００１１】最後に、最適化手段１２０５は、以上の情
報に基づき、最適化を実行する。この例では、山登り法
による最適化を説明する。まず、ランダムに組合せ単位
を選択し、それを移動平面上で左または右に移動する。
移動する前のコストと移動した後のコストを比較し、コ
ストが低い状態を採用する。この操作を繰り返し、コス
トの低い組合せ単位の配置つまりスケジュールを探索し
ていき、満足のいく状態になったとき、停止する。その
時の配置が解となる。

【００１２】

【発明が解決しようとする課題】しかしながら、上記従
来の方法では、第１にスケジュールやレイアウトなどの
組合せ最適化問題に応じて作成の困難な最適化手段を含
めてすべての定義手段を作り直す必要があり、組合せ単
位定義手段では複雑な組合せ単位の形状を容易に作成で
きないという問題点があった。

【００１３】第２に、最適化手法に応じて、実行時間や
解の精度が異なるにも関わらず、最適化手法を問題に応
じて選択できないという問題点があった。

【００１４】本発明は、上記問題点に鑑み、第１に、組
合せ最適化問題で共通な最適化手段とその他の部分を分
離して、異なる組合せ最適化問題を容易に解決でき、移
動平面と組合せ単位を視覚的に容易に定義できるように
した組合せ最適化装置を提供することを目的とするもの
である。

【００１５】本発明は第２に、最適化手法を複数用意し
て、問題に応じた最適化手法を自由に選択できるように
した組合せ最適化装置を提供することを目的とするもの
である。

【００１６】

【課題を解決するための手段】本発明は、上記第１の目
的を達成するため、組合せ単位が移動する平面である移
動平面の形状と移動平面上の点の名称を視覚的に定義す
る視覚的移動平面定義手段と、移動平面上を移動する組
合せ単位の形状と組合せ単位上の点の名称を視覚的に定
義する視覚的組合せ単位定義手段と、移動平面上を組合
せ単位が移動できる種類を定義する移動種類定義手段
と、移動平面上の組合せ移動単位の位置に対応して組合
せの善し悪しの尺度であるコストを定義するコスト定義
手段と、これら各定義手段により定義された情報に基づ
き、コストが極大または極小となる移動平面上の組合せ
単位の最適な配置と最適な組合せを求める自動最適化手
段とを備えたものである。

【００１７】本発明は、上記第２の目的を達成するた
め、自動最適化手段が、最適化時間により任意に最適化
方法を選択できる最適化方法選択手段を備えたものであ
る。

【００１８】

【作用】本発明は、上記第１の構成によって、組合せ最
適化問題によって異なる移動平面を定義する手段と組合
せ単位を定義する手段と移動種類を定義する手段と、こ
れらに対し組合せ単位の最適な配置と最適な組合せを求
める共通な最適化手段とを分離し、異なる組合せ最適化
問題でも移動平面の定義、組合せ単位の定義、移動種類
の定義を変更するだけで、作成の難しい最適化手段を意
識することなく、解を得ることができる。また、移動平
面や組合せ単位の形状や特別な点の名称を視覚的に容易
に定義することができる。

【００１９】本発明は、上記第２の構成によって、組合
せ最適化問題に応じた適切な最適化手法を選択すること
ができる。

【００２０】

【実施例】

（実施例１）以下、図面を参照しながら本発明の第１の
実施例について説明する。図１は本発明の第１の実施例
における組合せ最適化装置の構成を示すブロック図であ
る。図１において、１０１は視覚的移動平面定義手段、
１０２は視覚的組合せ単位定義手段、１０３は移動種類
定義手段、１０４はコスト定義手段、１０５は自動最適
化手段である。

【００２１】以上のような構成を備えた組合せ最適化装
置において、以下、その動作について説明する。組合せ
最適化装置の使用者は、まず、図１の視覚的移動平面定
義手段１０１によって、図２に示す移動平面の形状と移
動平面特別点を定義する。図２は移動平面の形状を定義
している。具体的な方法としては、マウスなどの入力装
置を使用して、移動平面作成面２０１の上に移動平面２
０２の形状を定義する。また、ある点に対して、制約条
件を与えるために、移動平面特別点２０３を定義する。
例えば、レイアウト問題などを想定した場合、柱の位置
や窓の位置を移動平面特別点とする。

【００２２】次に使用者は、図１の視覚的組合せ単位定
義手段１０２により、組合せ単位を定義する。図３は、
組合せ単位の定義手段を示す図である。図２の移動平面
２０２のように、視覚的移動平面定義手段１０１で定義
された移動平面が図３に示す移動平面３０１である。移
動平面３０１の点は、左上を原点として、Ｘ座標とＹ座
標を対応させる。組合せ単位（１）３０２と組合せ単位
（２）３０３が、定義された組合せ単位である。図４は
組合せ単位を示した図である。組合せ単位４０１の座標
も移動平面と同様に、左上を原点とする。組合せ単位特
別点（１）４０２と組合せ単位特別点（２）４０３も定
義される。

【００２３】上記動作を従来例で示したスケジュール問
題を解く方法について応用してみる。まず図５に示すよ
うに、視覚的移動平面定義手段１０１により、移動平面
作成面５０１上にスケジュール問題の移動平面５０２を
定義する。次いで図６に示すように、視覚的組合せ単位
定義手段１０２により、定義された移動平面５０２であ
る移動平面６０１上に組合せ単位であるblock1(602),bl
ock2(603),block3(604),block4(605) を定義する。ま
た、組合せ単位特別点であるblock1.right(606),block
2.left(607),block2.right(608),block3.left(609),blo
ck3.right(610) とblock4.left(611)も同様に定義され
る。移動平面６０１は、スケジュール表を示し、組合せ
単位（６０２〜６０５）は、仕事を示している。

【００２４】次に移動種類定義手段１０３により、組合
せ単位が移動できる種類を以下のように決定する。

【００２５】上記記述において、begin ｛movement｝か
らend ｛movement｝までの範囲が移動種類定義手段１０
３により定義された記述である。begin ｛block1｝から
end｛block1｝までの範囲がblock1つまり仕事１に関す
る記述である。x-direction= on; という記述は、block
1がＸ軸方向に動く自由度があることを示している。y-d
irection = off;という記述は、Ｙ軸方向に動く自由度
がないということを示している。rotation = off; とい
う記述は、block1が、回転する自由度がないということ
を示している。つまり、このスケジューリング問題は、
組合せ単位のＸ軸方向の適当な配置を決定する問題とし
て表現できる。

【００２６】次にコスト定義手段１０４により、組合せ
の良し悪しの尺度を決定するコストを以下のうように定
義する。 begin ｛cost｝ cost = 0; if(not(get-x-point(block1. 3,0 ) < get-x-point(block3. 0,0 ))) cost = cost + 50; if(not(get-x-point(block3. 2,0 ) < get-x-point(block2. 0,0 ))) cost = cost + 50; if(not(get-x-point(block2. 2,0 ) + 2 < get-x-point(block4. 0,0 ) )) cost = cost + 50; end ｛cost｝

【００２７】上記記述において、begin ｛cost｝からen
d ｛cost｝までが、コストの定義に関する記述である。
block1. 3,0 は、block1のＸ座標が３、Ｙ座標が０を示
す。get-x-point(block1. 3,0 ) という関数は、その点
の移動平面でのＸ座標を求める関数である。not(get-x-
point(block1. 3,0 ) < get-x-point(block3. 0,0 ))
は、block1がblock3より同じか右側にあることを示して
おり、そのとき、コストは５０加算される。これは、次
の制約条件を表現している。・仕事３は、仕事１が終了した後に実行する。このように、コストが高い程、制約条件が満たされてい
ないことを示している。この問題を解くためには、cost
= 0の組合せ単位の配置を求めることである。また、直
接、座標を入力するのではなく、組合せ単位特別点とし
て、入力すれば、定義しやすく、理解しやすい形式にな
る。組合せ単位特別点で表現すると以下のようになる。 begin ｛cost｝ cost = 0; if(not(get-x-point(block1.right) < get-x-point(block3.left))) cost = cost + 50; if(not(get-x-point(block3.right) < get-x-point(block2.left))) cost = cost + 50; if(not(get-x-point(block2.right) + 2 < get-x-point(block4.left)) ) cost = cost + 50; end ｛cost｝使用者は、以上の情報だけを定義する。以後の処理は、
自動最適化手段１０５が最適化を自動的に実行する。最
適化の手法は、いろいろ考えられるが、本実施例では、
山登り法によるアルゴリズムを説明する。まず、組合せ
最適化単位をランダムに１つ選択する。それを移動平面
上で移動種類の定義に従って、移動できる場所をランダ
ムに選択する。その新しい配置に対して、コスト定義に
従って、コストを計算する。もし、新しいコストが、移
動前のコストより低いならば、新しい配置を採用する。
この操作を繰り返し行なうことで、コストの低い最適な
配置を求めていく。最終的に得られた最適化結果が、図
７である。

【００２８】以上のように、上記第１の実施例によれば
処理が困難な最適化手法を知らなくても、使用者は、問
題に応じた部分を簡単に定義するだけで、組合せ最適化
問題を解くことが可能である。また、定義方法を視覚的
に示したことで、容易に問題に応じた移動平面や組合せ
単位の形状を定義することが可能である。

【００２９】（実施例２）次に、図８、図９および図１
０を参照しながら本発明の第２の実施例について説明す
る。この第２の実施例では、本発明をレイアウト問題に
適用した例を示す。装置の構成は図１と同じなので、動
作についてのみ述べる。

【００３０】本実施例における、レイアウト問題は次の
ような問題である。・部品１と部品２は、部品３から遠ざけたい。・部品１と部品２を近くに置きたい。

【００３１】最初に、図８に示すように、移動平面作成
面８０１上で移動平面８０２を作成する。具体的には、
プリント基板のようなものが想定できる。次に、図９に
示すように、各組合せ単位の形状を定義する。定義され
た組合せ単位が、block1（９０２）、block2（９０
３）、block3（９０４）である。さらに、組合せ単位上
に組合せ単位特別点を定義する。定義された組合せ単位
特別点は、block1.center（９０５）、block2.center
（９０６）、block3.center （９０７）である。

【００３２】次に移動種類を定義する。

【００３３】上記各組合せ単位は、xy軸の両方向に移動
できることを示しており、回転も可能なことを示してい
る。次に、コストは、以下のように定義される。 begin ｛cost｝ cost = 0; cost = cost + 1/distance(block1.center, block3.center); cost = cost + 1/distance(block2.center, block3.center); cost = cost + distance(block1.center, block2.center); end ｛cost｝ distanceは、ある点とある点との距離を求める関数であ
る。この定義に基づいて、自動最適化手段１０５が最適
化を実行する。図１０は最適化された結果である。

【００３４】以上のように、上記第２の実施例によれ
ば、処理が困難な最適化手法を知らなくても、使用者
は、問題に応じた部分を簡単に定義するだけで、組合せ
最適化問題を解くことが可能である。また、定義方法を
視覚的にしたことで、容易に問題に応じた移動平面や組
合せ単位の形状を定義することが可能である。

【００３５】（実施例３）次に、図１１を参照して本発
明の第３の実施例について説明する。この第３の実施例
では、図１における自動最適化手段１０５の代わりに、
最適化方法選択手段１１０１を有する自動最適化手段１
０５Ａを使用する。

【００３６】以上のような構成において、以下、その動
作について説明する。最適化手法は、高速な手法は最適
な解が得られにくく、最適な解を得るには、処理時間を
多く必要とするため、どのような問題でも適用できる万
能な手法は、存在しない。そのため、最適化を実行する
とき、図１１に示す最適化方法選択手段１１０１によ
り、適切な最適化方法を選択して、最適化を実行する。
図１１では、シミュレーティッド・アニーリングという
手法が選択されている。

【００３７】以上のように、上記第３の実施例によれ
ば、自動最適化手段１０５Ａが、最適化方法選択手段１
１０１を備えることにより、使用者が選択する最適化時
間により、任意に最適化方法を選択できる。

【００３８】

【発明の効果】本発明は、上記各実施例から明らかなよ
うに、第１の効果は、処理が困難な最適化手法を知らな
くても、使用者は、問題に応じた部分を簡単に定義する
だけで、組合せ最適化問題を解くことができることであ
る。また、定義方法を視覚的にしたことで、容易に問題
に応じた移動平面や組合せ単位の形状を定義することが
可能である。

【００３９】また本発明の第２の効果は、自動最適化手
段が最適化方法選択手段を備えることにより、使用者が
選択する最適化時間により、任意に最適化方法を選択で
きることである。

【図面の簡単な説明】

【図１】本発明の第１および第２の実施例における組合
せ最適化装置の構成を示すブロック図

【図２】本発明の第１の実施例における視覚的移動平面
定義手段の動作を説明するための模式図

【図３】本発明の第１の実施例における視覚的組合せ単
位定義手段の動作を説明するための模式図

【図４】本発明の第１の実施例における組合せ単位の模
式図

【図５】本発明の第１の実施例におけるスケジュール問
題の視覚的移動平面定義手段の作動を説明するための模
式図

【図６】本発明の第１の実施例におけるスケジュール問
題の視覚的組合せ単位定義手段の動作を説明するための
模式図

【図７】本発明の第１の実施例における最適化された結
果を示す模式図

【図８】本発明の第２の実施例における視覚的移動平面
定義手段の動作を説明するための模式図

【図９】本発明の第２の実施例における視覚的組合せ単
位定義手段の動作を説明するための模式図

【図１０】本発明の第２の実施例における最適化された
結果を示す模式図

【図１１】本発明の第３の実施例における組合せ最適化
装置の構成を示すブロック図

【図１２】従来の組合せ最適化装置の構成を示すブロッ
ク図

【符号の説明】

１０１視覚的移動平面定義手段１０２視覚的組合せ単位定義手段１０３移動種類定義手段１０４コスト定義手段１０５、１０５Ａ自動最適化手段１１０１最適化方法選択手段

───────────────────────────────────────────────────── フロントページの続き (72)発明者野島晋二大阪府門真市大字門真1006番地松下電器産業株式会社内

Claims

【特許請求の範囲】

【請求項１】組合せ単位が移動する平面である移動平
面の形状と移動平面上の点の名称を視覚的に定義する視
覚的移動平面定義手段と、前記移動平面上を移動する組
合せ単位の形状と組合せ単位上の点の名称を視覚的に定
義する視覚的組合せ単位定義手段と、前記移動平面上を
前記組合せ単位が移動できる種類を定義する移動種類定
義手段と、前記移動平面上の前記組合せ移動単位の位置
に対応して組合せの善し悪しの尺度であるコストを定義
するコスト定義手段と、前記各定義手段により定義され
た情報に基づき、コストが極大または極小となる移動平
面上の組合せ単位の最適な配置と最適な組合せを求める
自動最適化手段とを備えた組合せ最適化装置。
【請求項２】自動最適化手段が、最適化時間により任
意に最適化方法を選択できる最適化方法選択手段を備え
ていることを特徴とする請求項１記載の組合せ最適化装
置。