(57)【特許請求の範囲】
【請求項１】
多目標最適化装置であって、
遺伝的アルゴリズムにより、第ｉ世代の方案集に対してランキング、選択、交叉、突然変異を行って第一方案集を生成するための第一生成ユニット；
前記第一方案集の中の方案と、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とを合併してランキングすることにより、前記第一方案集の中の方案の優先順位を更新し、前記第一方案集の中の方案と同じであり且つ方案の優先順位が更新された第二方案集を得るための第一処理ユニット；
前記第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集に基づいて、第一最適方案集を確定するための第一確定ユニット；及び
前記第一最適方案集の中の方案により前記第二方案集の中の方案を置換し、第一所定条件を満足したときに、第i+1世代の方案集を得るための第二処理ユニットを含む、装置。
【請求項２】
請求項1に記載の装置であって、
前記第一確定ユニットは、前記第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の、優先順位が最高であり且つ前記第一処理ユニットにより合併、ランキングされた後の優先順位が未変更である方案を、前記第一最適方案集の中の方案と確定する、装置。
【請求項３】
請求項2に記載の装置であって、
前記第二処理ユニットは、
前記第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在するかを判断するための第一判断ユニット；
前記第一判断ユニットの判断結果が「はい」のときに、前記第二方案集の中の方案の優先順位の「低いものから高いものへ」の順序に従って、前記第一最適方案集の中の前記第二方案集に存在しない第一最適方案により、前記第二方案集の中の優先順位が最高である方案以外の他の方案を置換するための第一置換ユニット；
前記第一判断ユニットの判断結果が「いいえ」のときに、前記第二方案集には優先順位が最高である重複方案が存在するかを判断するための第二判断ユニット；
前記第二判断ユニットの判断結果が「はい」のときに、前記第一最適方案集の中の前記第二方案集に存在しない第二最適方案により、前記第二方案集の中の優先順位が最高である重複方案を置換するための第二置換ユニット；及び
前記第二判断ユニットの判断結果が「いいえ」のときに、前記第一最適方案集の中の前記第二方案集に存在しない第三最適方案により、前記第二方案集の中の優先順位が最高である方案を置換するための第三置換ユニットを含む、装置。
【請求項４】
請求項1に記載の装置であって、
前記第一所定条件は、前記第一最適方案集に残りの最適方案が存在せず、又は、前記第二方案集の中の置換され得る方案がすべて置換されたということであり、
前記第一所定条件を満足したときに、前記第二処理ユニットは、置換後に得られた第二方案集を第i+1世代の方案集とする、装置。
【請求項５】
請求項1に記載の装置であって、
前記方案は、無線ネットワーク計画方案である、装置。
【請求項６】
無線ネットワーク計画装置であって、
遺伝的アルゴリズムにより、第ｉ世代の無線ネットワーク計画方案集に対してランキング、選択、交叉、突然変異を行って第一計画方案集を生成するための第二生成ユニッ；
前記第一計画方案集の中の方案と、第0世代から第ｉ世代までの無線ネットワーク計画方案集のうちの１世代又は１世代以上の計画方案集の中の優先順位が高い計画方案とを合併してランキングすることにより、前記第一計画方案集の中の計画方案の優先順位を更新し、前記第一計画方案集の中の計画方案と同じであり且つ計画方案の優先順位が更新された第二計画方案集を得るための第三処理ユニット；
前記第0世代から第ｉ世代までの無線ネットワーク計画方案集のうちの１世代又は１世代以上の計画方案集に基づいて、第一最適化計画方案集を確定するための第二確定ユニット；
前記第一最適化計画方案集の中の計画方案により前記第二計画方案集の中の計画方案を置換し、第一所定条件を満足したときに、第i+1世代の無線ネットワーク計画方案集を得るための第四処理ユニット；及び
第二所定条件を満足したときに、前記第i+1世代の無線ネットワーク計画方案集を最終無線ネットワーク計画方案集と確定するための第五処理ユニットを含む、装置。
【請求項７】
多目標最適化方法であって、
遺伝的アルゴリズムにより、第ｉ世代の方案集に対してランキング、選択、交叉、突然変異を行って第一方案集を生成し；
前記第一方案集の中の方案と、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とを合併してランキングすることにより、前記第一方案集の中の方案の優先順位を更新し、前記第一方案集の中の方案と同じであり且つ方案の優先順位が更新された第二方案集を取得し；
前記第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集に基づいて得られた第一最適方案集の中の方案により前記第二方案集の中の方案を置換し、第一所定条件を満足したときに、第i+1世代の方案集を得ることを含む、方法。
【請求項８】
請求項7に記載の方法であって、
前記第一最適方案集の中の方案とは、前記第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の、優先順位が最高であり且つ合併、ランキング後の優先順位が未変更である方案を指す、方法。
【請求項９】
請求項8に記載の方法であって、
前記第一最適方案集の中の方案により前記第二方案集の中の方案を置換することは、
前記第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在するときに、前記第二方案集の中の方案の優先順位の「低いものから高いものへ」の順序に従って、前記第一最適方案集の中の前記第二方案集に存在しない第一最適方案により、前記第二方案集の中の優先順位が最高である方案以外の他の方案を置換し；
前記第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在せず且つ前記第二方案集には優先順位が最高である重複方案が存在するときに、前記第一最適方案集の中の前記第二方案集に存在しない第二最適方案により、前記第二方案集の中の優先順位が最高である重複方案を置換し；及び
前記第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在せず且つ前記第二方案集には優先順位が最高である重複方案も存在しないときに、前記第一最適方案集の中の前記第二方案集に存在しない第三最適方案により、前記第二方案集の中の優先順位が最高である方案を置換することを含む、方法。
【請求項１０】
請求項7に記載の方法であって、
第一所定条件を満足したときに、第i+1世代の方案集を得ることは、
前記第一最適方案集には残りの最適方案が存在せず、又は、前記第二方案集の中の置換され得る方案がすべて置換されたときに、置換後に得られた第二方案集を第i+1世代の方案集とすることを含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信技術分野に関し、特に、多目標最適化方法及び装置に関する。
【背景技術】
【０００２】
無線通信技術の発展により、ユーザがいつでもどのでもネットワークにアクセスし得るようになっている。WLAN（Wireless  Local  Area  Networks）は、IEEE（Institute  of  Electrical  and  Electronics  Engineers)802.11規格に基づく無線通信技術である。IEEE  802.11規格では、３種類のネットワークモデルを提供している。そのうち、アクセスポイント（Access  Point、AP）によりネットワークを構成するモデルは、最も広く応用されており、そのインフラストラクチャーモデル（infrastructure  model）は、APを中心として構成されたシングルホップネットワークである。該ネットワークモデルでは、ユーザ（User）がAPに直接接続され、APは該ユーザにサービスを提供する。また、ネットワークのパフォーマンスは、APの数量、位置、使用するチャネル、及び送信電力（Power）の計画に依存する。
【０００３】
APモデルは多項式時間で解く方法がないので、遺伝的アルゴリズムなどの発見的アルゴリズムを採用して無線ネットワーク計画問題を解決するのが最適である。遺伝的アルゴリズムは、“選択、交叉、突然変異”などの幾つかの基本操作を含み、その基本思想は、自然界の“物競天択、適者生存”に模倣したものである。そのうち、“選択”操作では，母集団（ここでは、計画方案集又は方案集とも称される）の中の各個体（ここでは、計画方案又は方案とも称される）の評価値（例えば、適応度による確率）に従って次世代への生き残りやすさを求め、これに基づいて次世代の母集団を形成する。“交叉、変異”操作では、新しい個体を取り入れて母集団の多様性を維持し、これによって母集団からより優れた個体が生まれるようにさせる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
遺伝的アルゴリズムでは、選択操作は、確率に基づくものであるため、一定の偶然性を有する。選択操作は、優れた個体がより高い被選択機会を得るように保証することができるが、全ての優れた個体が次世代に生き残ることを保証することができない。よって、選択操作では、幾つかの優れた個体が“選択”されないため次世代の母集団に含まれず、他の優れた個体の該母集団における数量がどんどん多くなる可能性がある。また、交叉、突然変異操作では、幾つかの優れた個体を破壊するおそれもある。これらの問題は、アルゴリズムの最適化の速度に影響を与えることがあるのみならず、アルゴリズムが局所最適に陥り、適応度が後退する現象を来すこともある。
【０００５】
本発明の実施例は、多目標最適化方法及び装置を提供し、遺伝的アルゴリズムに“エリート保留”というポリシーを取り入れることで、第0世代（最初の世代）から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の最適方案（エリート）を用いて、選択、交叉、突然変異後の第ｉ世代の方案集の中の方案を置換し、これにより、遺伝的アルゴリズムの反復過程における前の幾つかの世代の優れた方案を次世代の方案集に保留させることができ、交叉、突然変異操作で比較的優れた方案を破壊しないように確保することができる。
【課題を解決するための手段】
【０００６】
上述した目的は、次のような技術案により実現される。
【０００７】
本発明の実施例の第一側面によれば、多目標最適化装置が提供され、該装置は、
遺伝的アルゴリズムを用いて、第ｉ世代の方案集に対してランキング、選択、交叉、突然変異を行った後に第一方案集を生成するための第一生成ユニット；
第一方案集の中の方案と、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とを合併してランキングすることで、該第一方案集の中の方案の優先順位を更新し、該第一方案集の中の方案と同じであるが、方案の優先順位が更新された第二方案集を得るための第一処理ユニット；
該第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集に基づいて、第一最適方案集を確定するための第一確定ユニット；及び
該第一最適方案集の中の方案を用いて該第二方案集の中の方案を置換し、第一所定条件を満足したときに、第i+1世代の方案集を得るための第二処理ユニットを含む。
【０００８】
本発明の実施例の第二側面によれば、無線ネットワーク計画装置が提供され、該装置は、
遺伝的アルゴリズムを用いて、第ｉ世代の無線ネットワーク計画方案集に対してランキング、選択、交叉、突然変異を行った後に第一方案集を生成するための第二生成ユニット；
該第一計画方案集の中の方案と、第0世代から第ｉ世代までの無線ネットワーク計画方案集のうちの１世代又は１世代以上の計画方案集の中の優先順位が高い計画方案とを合併してランキングすることで、該第一計画方案集の中の計画方案の優先順位を更新し、該第一計画方案集の中の計画方案と同じであるが、計画方案の優先順位が更新された第二計画方案集を得るための第三処理ユニット；
該第0世代から第ｉ世代までの無線ネットワーク計画方案集のうちの１世代又は１世代以上の計画方案集に基づいて、第一最適化計画方案集を確定するための第二確定ユニット；
該第一最適化計画方案集の中の計画方案を用いて該第二計画方案集の中の計画方案を置換し、第一所定条件を満足したときに、第i+1世代の無線ネットワーク計画方案集を得るための第四処理ユニット；及び
第二所定条件を満足したときに、該第i+1世代の無線ネットワーク計画方案集を最終無線ネットワーク計画方案集として確定するための第五処理ユニットを含む。
【０００９】
本発明の実施例の第三側面によれば、多目標最適化方法が提供され、該方法は、
遺伝的アルゴリズムを用いて、第ｉ世代の方案集に対してランキング、選択、交叉、突然変異を行った後に第一方案集を生成し；
該第一方案集の中の方案と、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とを合併してランキングすることで、該第一方案集の中の方案の優先順位を更新し、該第一方案集の中の方案と同じであるが、方案の優先順位が更新された第二方案集を取得し；及び
該第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集に基づいて取得された第一最適方案集の中の方案を用いて、該第二方案集の中の方案を置換し、第一所定条件を満足したときに、第i+1世代の方案集を得ることを含む。
【００１０】
本発明の実施例の有益な効果は、本発明の実施例における多目標最適化方法及び装置により、遺伝的アルゴリズムの反復過程における前の幾つかの世代の比較的優れた方案を次世代の方案集に保留させることができ、比較的優れた方案への交叉、突然変異操作による破壊を防止することができる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施例1における多目標最適化方法のフローチャートである。
【図２】本発明の実施例1における多目標最適化方法のフローチャートである。
【図３】本発明の実施例3における多目標最適化方法のフローチャートである。
【図４】本発明の実施例3におけるステップ204の具体的な実施方法のフローチャートである。
【図５】本発明の実施例4における無線ネットワーク計画方法のフローチャートである。
【図６】本発明の実施例5における多目標最適化装置の一実施方式の構成図である。
【図７】本発明の実施例5における第二処理ユニット604の構成図である。
【図８】本発明の実施例5における多目標最適化装置の他の実施方式の構成図である。
【図９】本発明の実施例6における無線ネットワーク計画装置の一実施方式の構成図である。
【図１０】本発明の実施例6における無線ネットワーク計画装置の他の実施方式の構成図である。
【発明を実施するための形態】
【００１２】
以下、添付した図面を参照しながら、本発明を実施するための形態を詳細に説明する。
【００１３】
なお、当業者が本発明の原理及び実施形態を容易に理解し得るために、本発明の実施例では、無線ネットワーク計画を例として説明を行っているが、理解すべきは、本発明の実施例は、無線ネットワーク計画に限られず、例えば、本発明の実施例による方法及び装置は、遺伝的アルゴリズムを用いて多目標最適化を行う他のシナリオにも適用し得るということである。
【実施例１】
【００１４】
図1は本発明の実施例1における多目標最適化方法のフローチャートである。図1に示すように、該方法は次のステップを含む。
【００１５】
ステップ101：遺伝的アルゴリズムを用いて、第ｉ世代の方案集に対してランキング、選択、交叉、突然変異を行って第一方案集を生成し；
ステップ102：該第一方案集の中の方案と、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とを合併してランキングすることで、該第一方案集の中の方案の優先順位を更新し、該第一方案集の中の方案と同じであるが、方案の優先順位が更新された第二方案集を取得し；
ステップ103：該第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集に基づいて得られた第一最適方案集の中の方案を用いて、該第二方案集の中の方案を置換し、第一所定条件を満足したときに、第i+1世代の方案集を得る。
【００１６】
本実施例から分かるように、該第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の第一最適方案集を確定し、そして、第一最適方案集の中の方案を用いて第二方案集の中の方案を置換することにより、遺伝的アルゴリズムの反復過程中における前の幾つかの世代の比較的優れた方案を次世代の方案集に保留させることができ、比較的優れた方案への交叉、突然変異操作による破壊を防止することができる。
【００１７】
本実施例では、iの値は、非負の整数であり、i=0の時には、ステップ101では、現在の方案集は第0世代の方案集であることを表し、ステップ102及び103では、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案は、第0世代の方案集の中の優先順位が高い方案であることを表す。
【００１８】
本実施例では、ステップ101は、遺伝的アルゴリズムを用いて第ｉ世代の方案集に対して処理を行い、具体的には、適応度関数を計算し、パレートランキング法を用いて該第ｉ世代の方案集のうちの各方案に優先順位（遺伝的アルゴリズムのランキング処理）を設定し；設定された優先順位に基づいて、各方案の選択の確率を計算し；計算された各方案の選択の確率に基づいて、第ｉ世代の計画方案集から第一所定数量の方案を選択し（遺伝的アルゴリズムの選択処理）、選択された第一所定数量の方案から第二所定数量組の方案を選定し、そのうち、各組の方案は２つの方案を含み、各組の方案の中の２つの方案のうちの所定位置の方案を交換し（遺伝的アルゴリズムの交叉処理）；交叉処理後の方案集から第三所定数量の方案を確定し、第三所定数量の方案の中の各方案のうちの所定位置の方案を、その現在の方案と異なる方案（遺伝的アルゴリズムの突然変異処理）に変えることで、第一方案集を得ることを含む。
【００１９】
本実施例では、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の第一最適方案集を確定するために、ステップ102の前に、該方法はさらに、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案を確定することを含む。
【００２０】
そのうち、該優先順位は、ステップ101でのパレートランキング方法により確定され、例えば、パレートランキング方法により各方案の優先順位RANKを確定するとする。通常、RANK=1を用いて優先順位が一番高いことを表し、RANK=2を用いて優先順位が二番目に高いことを表し、そして、これに基づいて類推することができる。なお、その逆も同じである。
【００２１】
本実施例では、例えば、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の計N個の優先順位のうちの前のm1個の優先順位の方案を、優先順位が高い方案と確定しても良く；例えば、m1=1の時に、RANK=1の方案を、優先順位が高い方案と確定しても良く、m1=2の時に、RANK=1及びRANK=2の方案を、優先順位が高い方案と確定しても良く、そして、これに基づいて類推することができる。なお、本実施例は、これに限定されない。
【００２２】
ステップ102では、該第一方案集の中の方案と、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とを合併してランキングすることで、該第一方案集の中の方案の優先順位を更新し、該第一方案集の中の方案と同じであるが、方案の優先順位が更新された第二方案集を得る。
【００２３】
そのうち、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案は、第0世代から第ｉ世代までの方案集のうちの任意のm2世代の方案集の中の優先順位が高い方案であっても良く、例えば、m2=1の時に、第0世代の方案集の中の優先順位が高い方案であっても良く、又は、第ｉ世代の方案集の中の優先順位が高い方案であっても良く、又は、第i-1世代の方案集の中の優先順位が高い方案であっても良く、本実施例では、好ましくは、第ｉ世代の方案集の中の優先順位が高い方案を選択し；例えば、m2=2の時に、第ｉ世代及び第i-1世代の方案集の中の優先順位が高い方案であっても良く、第i-1世代及び第i-3世代の方案集の中の優先順位が高い方案であっても良く；そして、これに基づいて類推することができる。なお、本実施例では、これに限定されず、m2は、[1,i+1]のうちの任意の整数であっても良い。
【００２４】
ステップ102では、第一方案集の中の方案と、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とに対して合併、ランキングのみ行う。このように、ランキングに参与する方案が変化しているので、第一方案集の中の方案の優先順位は、ステップ101での優先順位と比べ、変化が生じる可能性がある。本実施例では、優先順位が更新された後の第一方案集を第二方案集と称する。よって、第二方案集の中の方案は、第一方案集の中の方案と同じであり、方案の優先順位のみ更新された。
【００２５】
本実施例では、ステップ103の前に、該方法はさらに、該第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集に基づいて、第一最適方案集を得ることを含み、そのうち、第一最適方案集の中の最適方案は、“エリート”と称されても良く、そのうち、該第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が最高であり、且つ、ステップ102での合併、ランキング後の優先順位が未変更である方案を、第一最適方案集の中の方案として確定する。本実施方式から分かるように、第一最適方案集の中の最適方案が、合併、ランキング後に優先順位が依然として最高である方案であるため、このような方案を最適方案とすることにより、選択されたエリートのパフォーマンスが比較的優れたものであるようにさせることができ、例えば、無線ネットワーク計画時に、ネットワークパフォーマンスが比較的優れた計画方案を得ることができる。
【００２６】
本実施例では、第一最適方案集を得た後に、ステップ103において該第一最適方案集の中の方案により該第二方案集の中の方案を置換し、第一所定条件を満足したときに、第i+1世代の方案集を得る。これにより、遺伝的アルゴリズムの反復過程における前の幾つかの世代の最適方案を第i+1世代の方案集に保留させることができ、交叉、突然変異操作による最適方案への破壊を避け、エリート保留を実現することができる。
【００２７】
本実施例では、該第一所定条件は、該第一最適方案集に残りの最適方案が存在せず、又は、該第二方案集の中の置換され得る方案がすべて置換されたということであっても良く、ステップ103では、該第一所定条件を満足したときに、置換後に得られた第二方案集を第i+1世代の方案集とする。
【００２８】
そのうち、第一最適方案集に残りの最適方案が存在しないことは、該第一最適方案集には、該第二方案集に存在せず且つ置換に参与していない最適方案が無いということを指す。該第二方案集の中の置換され得る方案とは、第二方案集の中の、優先順位が最高である方案以外の他の低い優先順位の方案、優先順位が最高である重複方案、及び他の優先順位が最高である方案を指す。
【００２９】
以下、便宜のため、第ｉ世代の方案集の中の、優先順位が最高である、即ち、RANK=1である方案を、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とすることを例とし、本実施例における多目標最適化方法について説明する。
【００３０】
図2は本実施例における多目標最適化方法のフローチャートであり、そのうち、第ｉ世代の方案集は、母集団P1と表され、第一方案集は、母集団P2と表され、第二方案集は、母集団P2’と表され、第i+1世代の方案集は、母集団P3と表され、各方案集の中の方案は、個体と表され、母集団P1は、5つの個体I1、I2、I3、I4、I5からなる。
【００３１】
例えば、ステップ101では、遺伝的アルゴリズムを用いて、母集団P1に対してランキング、選択、交叉、突然変異を行った後に母集団P2を生成し、そのうち、P2は、3つのP1の中の個体I1、I4、I5を含み、また、交叉、突然変異後に２つの新個体I6及びI7が取り入れられ；そのうち、母集団P1は、ランキング後に、その各個体の優先順位がR1=2、R2=2、R3=1、R4=2、R5=3である。
【００３２】
ステップ102では、母集団P1の中の方案のうちの優先順位が最高である1つの個体I3と、母集団P2の中の個体とを合併してランキングし、即ち、個体I1、I4、I5、I6、I7、I1、I3に対して再びランキングを行い、R1’=2、R3’=1、R4’=2、R5’=3、R6’=1、R7’=2を取得し、これにより、母集団P2の中の個体の優先順位を更新し、母集団P2’を取得し、母集団P2’のうちの母集団P2と同じ個体I1、I4、I5、I6、I7の優先順位は、R1’=2、R4’=2、R5’=3、R6’=1、R7’=2と更新されている。
【００３３】
ステップ103では、P1の中の優先順位がRANK=1であるI3は、ステップ102の再ランキング後に、優先順位が依然としてRANK=1であるため、I3をエリートとし、P2’の中の個体、例えば、I5を置換することで、個体I1、I3、I4、I6、I7を含む新母集団P3を生成し；残りのエリートが存在しないため、即ち、第一所定条件を満足しているため、P3の中の個体I1、I3、I4、I6、I7を次世代の方案集とする。
【００３４】
以上、m1=1即ちRANK=1の方案を、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とすることを例として、本実施例における多目標最適化方法について説明したが、このような処理は、優先順位が高い方案、例えば、m1=2又はm1が他の値に等しいときの多目標最適化方法にも適用し得るので、ここではその詳しい説明を省略する。
【００３５】
本実施例では、遺伝的アルゴリズムに“エリート保留”ポリシーを取り入れ、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の最適方案（エリート）を用いて、選択、交叉、突然変異後の第ｉ世代の方案集の中の方案を置換することにより、遺伝的アルゴリズムの反復過程における前の幾つかの世代の比較的優れた方案を次世代の方案集に保留させることができ、交叉、突然変異操作による比較的優れた方案への破壊を避けることができる。
【実施例２】
【００３６】
実施例1では、如何に第一最適方案集を確定するか、及び、ステップ101〜103での多目標最適化方法について説明した。本実施例2はさらに、改良された多目標最適化アルゴリズムを提供する。実施例1をもとに、ステップ103での第一最適方案集による最適方案の置換について改良することにより、遺伝的アルゴリズムの反復過程における前の幾つかの世代の最適方案の、第i+1世代の方案集への保留をより一層確保することができる。
【００３７】
本実施例2では、ステップ101〜102の具体的な実施方式は、実施例1と同じであるため、ここではその詳しい説明を省略する。
【００３８】
以下、ステップ103の具体的な実施方式について説明する。
【００３９】
一実施方式では、第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在する時に、該第二方案集の中の方案の優先順位の「低いものから高いものへ」の順序に従って、該第一最適方案集の中の、該第二方案集に存在しない第一最適方案を用いて、該第二方案集の中の優先順位が最高である方案以外の他の方案を置換する。これにより、エリート保留を実現し、パフォーマンスが比較的良くない方案を除去することができるため、パフォーマンスが比較的優れた方案を取得し、遺伝的アルゴリズムの反復の収束速度を加速することができる。
【００４０】
一実施方式では、第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在せず且つ該第二方案集には優先順位が最高である重複方案が存在する時に、該第一最適方案集の中の、該第二方案集に存在しない第二最適方案を用いて、該第二方案集の中の優先順位が最高である重複方案を置換する。これにより、エリート保留を実現し、重複した方案を除去し、方案集の中の方案の多様性を保つことができる。
【００４１】
一実施方式では、第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在せず且つ該第二方案集には優先順位が最高である重複方案も存在しない時に、該第一最適方案集の中の、該第二方案集に存在しない第三最適方案を用いて、該第二方案集の中の優先順位が最高である方案を置換する。これにより、エリート保留を実現し、交叉、突然変異操作による最適方案への破壊を避けることができる。
【００４２】
上述の実施方式により、遺伝的アルゴリズムの反復過程における前の幾つかの世代の比較的優れた方案の、次世代の方案集への保留をより一層確保することができるため、交叉、突然変異操作による比較的優れた方案への破壊を避け、方案集の中の方案の多様性を維持することができる。
【００４３】
以下、本実施例におけるステップ103の具体的に実施方式について例示的に説明する。ここでは、依然として図2を例とし、また、得られた第二方案集P2’の中の方案は、I1、I1、I4、I6、I7、I8であり、各方案の優先順位は、R1’=1、R1’=1、R4’=1、R6’=1、R7’=2、R8’=3であり、第一最適方案集の中の方案は、I1、I2、I3、I5、I9、I10、I11であるとする。なお、第二方案集を得る方法は、ステップ101〜102と同様であり、第一最適方案集を得る方法は、実施例1における第一最適方案集の取得方法と同様であるため、ここでは、重複説明を省略する。
【００４４】
例えば、P2’には優先順位が最高であるRANK=1の方案以外の他の低い優先順位の方案I7及びI8が存在するので、第一最適方案集の中の、P2’に存在しない方案I2及びI3を用いて、P2’の中のI8及びI7をそれぞれ置換し；また、P2’にはRANK=1の重複方案I1が依然として存在するので、第一最適方案集の中の残りの最適方案のうちの、P2’に存在しない方案I5を用いて、P2’の中の方案I1を置換し；この時に、P2’には他のRANK=1の方案I4、I6が依然として存在するので、第一最適方案集の中の残りの最適方案のうちの、P2’に存在しない方案I9、I10を用いて、P2’の中の方案I4、I6を置換し；この時に、第二方案集の中の置換され得る方案がすべて置換されたので、即ち、第一所定条件を満足したので、置換後の第二方案集I1、I5、I9、I10、I3、I2を第i+1世代の方案集とする。
【００４５】
本実施例では、I2、I3、I5、I9、I10の優先順位が同じであるため、方案I3及びI2を用いて、P2’の中のI8及びI7を置換し、I10を用いてP2’の中の方案I1を置換し、I5、I9を用いて、P2’の中の方案I4、I6を置換しても良く、本実施例ではこれについて限定しない。
【００４６】
本実施例では、ステップ101〜103での方案は、無線ネットワーク計画方案であっても良く、即ち、本実施例における多目標最適化方法は、無線ネットワーク計画に適用することができる。この場合、ネットワークパフォーマンスが最適である無線ネットワーク計画方案を得ることがでる。なお、その具体的な実施方式は、実施例4を参照することができるため、ここでは、その詳しい説明を省略する。
【００４７】
本実施例から分かるように、遺伝的アルゴリズムに“エリート保留”ポリシーを取り入れ、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の最適方案（エリート）を以て、選択、交叉、突然変異後の第ｉ世代の方案集の中の方案を置換することにより、遺伝的アルゴリズムの反復過程における前の幾つかの世代の比較的優れた方案の、次世代の方案集への保留を確保し、交叉、突然変異操作による比較的優れた方案への破壊を避けることができる。
【実施例３】
【００４８】
本発明の実施例3はさらに多目標最適化方法を提供する。図3は本実施例3における多目標最適化方法のフローチャートである。本実施例では、第ｉ世代の方案集の中の優先順位が最高である、即ち、RANK=1である方案のみを、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とすることを例とし、実施例1〜2における多目標最適化方法について例示的に説明する。図3に示すように、該方法は次のようなステップを含む。
【００４９】
ステップ301：第ｉ世代の方案集に対してパレートランキングを行い、優先順位が最高である、即ち、RANK=1である方案を確定し；
ステップ302：第ｉ世代方案集に対して選択、交叉、突然変異を行った後に、第一方案集を生成し；
ステップ303：第一方案集と、第ｉ世代の方案集から確定されたRANK=1の方案とを合併してランキングし、第ｉ世代の方案集の中の再ランキング後のRANKが依然として1である方案を、第一最適方案集の中の最適方案として保存し、そして、再ランキング後の第二方案集を取得し；
ステップ304：ステップ303で確定された第一最適方案集の中の最適方案を以て第二方案集の中の方案を置換し、第一所定条件を満足したときに、第i+1世代の方案集を取得し；
ステップ305：第i+1世代の方案集が第二所定条件を満足したかを判断し、第二所定条件を満足したときに、ステップ307を実行し、満足しない時に、ステップ306を実行し；
ステップ306：i＝i+1とし、ステップ301に戻し；
ステップ307：第i+1世代の方案集を最終方案集と確定する。
【００５０】
本実施例では、図4はステップ304での具体的な置換方法のフローチャートである。図4に示すように、ステップ304は次のようなステップを含む。
【００５１】
ステップ401：第一最適方案集には第二方案集に存在しない最適方案が存在するかを判断し、判断の結果がはいの場合、ステップ402を実行し、そうでない場合、処理を終了し；
ステップ402：第一最適方案集に存在するが、第二方案集に存在しない最適方案集Yを選択し；
ステップ403：第二方案集には優先順位が最高であるRANK=1の方案以外の他の低い優先順位（RANK＞1）の方案が存在するかを判断し、判断の結果がはいの場合、ステップ404を実行し、そうでない場合、ステップ406を実行し；
ステップ404：第二方案集の中の方案の優先順位の「低いものから高いものへ」の順序に従って、Yの中の第一最適方案を用いて、第二方案集の中のRANK＞1の方案を置換し、そして、置換に参与している第一最適方案をYから除去し；
ステップ405：最適方案集Yには残りの最適方案があるかを判断し、判断の結果がはいの場合、ステップ406を実行し、そうでない場合、処理を終了し；
ステップ406：第二方案集にはRANK=1の重複方案が存在するかを判断し、判断の結果がはいの場合、ステップ407を実行し、そうでない場合、ステップ409を実行し；
ステップ407：Yの中の残りの第二最適方案を以て第二方案集の中のRANK=1の重複方案を置換し、そして、置換に参与している第二最適方案をYから除去し；
ステップ408：最適方案集Yには残りの最適方案があるかを判断し、判断の結果がはいの場合、ステップ409を実行し、そうでない場合、処理を終了し；
ステップ409：第二方案集には他のRANK=1の方案が存在するかを判断し、判断の結果がはいの場合、ステップ410を実行し、そうでない場合、処理を終了し；
ステップ410：Yの中の残りの第三最適方案を用いて、第二方案集の中の他のRANK=1の方案を置換し、そして、置換に参与している第三最適方案をYから除去する。
【００５２】
本実施例では、ステップ301〜306及びステップ401〜410の具体的な実施方式は、実施例1及び2を参照することができるため、ここではその詳しい説明を省略する。
【００５３】
本実施例から分かるように、遺伝的アルゴリズムに“エリート保留”ポリシーを取り入れ、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の最適方案（エリート）を以て、選択、交叉、突然変異後の第ｉ世代の方案集の中の方案を置換することにより、遺伝的アルゴリズムの反復過程における前の幾つかの世代の比較的優れた方案の、次世代の方案集への保留を確保し、交叉、突然変異操作による比較的優れた方案への破壊を避けることができる。
【実施例４】
【００５４】
図5は本発明の実施例4における無線ネットワーク計画方法のフローチャートである。図5に示すように、該方法は、次のステップを含む。
【００５５】
ステップ501：遺伝的アルゴリズムを用いて、第ｉ世代の無線ネットワーク計画方案集に対して、ランキング、選択、交叉、突然変異を行った後に、第一計画方案集を生成し；
ステップ502：該第一計画方案集の中の計画方案と、第0世代から第ｉ世代までの無線ネットワーク計画方案集のうちの１世代又は１世代以上の計画方案集の中の優先順位が高い計画方案とを合併してランキングすることで、該第一計画方案集の中の計画方案の優先順位を更新し、該第一計画方案集の中の計画方案と同じであるが、計画方案の優先順位が更新された第二計画方案集を取得し；
ステップ503：該第0世代から第ｉ世代までの無線ネットワーク計画方案集のうちの１世代又は１世代以上の計画方案集に基づいて得られた第一最適化計画方案集の中の計画方案を用いて、該第二計画方案集の中の計画方案を置換し、第一所定条件を満足したときに、第i+1世代の無線ネットワーク計画方案集を取得し；
ステップ504：第二所定条件を満足したときに、該第i+1世代の無線ネットワーク計画方案集を最終無線ネットワーク計画方案集と確定する。
【００５６】
そのうち、第i+1世代の計画方案集を確定するステップ501〜503は、実施例1におけるステップ101〜103を参照することができるため、ここではその詳しい説明を省略する。
【００５７】
本実施例では、i=0の時に、該第ｉ世代の無線ネットワーク計画方案は、最初（first）計画方案集である。
【００５８】
本実施例では、まず、実施例1における方法で第ｉ世代（第0世代）の計画方案集に対して処理を行い、新しい計画方案集、即ち、第i+1世代（第1世代）の計画方案集を得る。第二所定条件を満足した場合、該第i+1世代の計画方案集を最終計画方案集とし、そうでない場合、生成された第i+1世代の計画方案集について、再びステップ501〜503での方法で第i+1世代の計画方案集に対して処理し、即ち、i＝1の場合に相当し、そして、このような処理を、最終計画方案を得るまで繰り返して行う。
【００５９】
そのうち、該第二所定条件は、i+1が所定の第一閾値に等しいということであっても良く、又は、i+1世代の無線ネットワーク計画方案集のうちの連続したm世代の計画方案集の中の各計画方案がすべて同じであるということであっても良く、そのうち、mは、予め設定された所定の第二閾値である。
【００６０】
本実施例から分かるように、遺伝的アルゴリズムに“エリート保留”ポリシーを取り入れ、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の最適方案（エリート）を以て、選択、交叉、突然変異後の第ｉ世代の方案集の中の方案を置換することで、遺伝的アルゴリズムの反復過程における前の幾つかの世代の比較的優れた方案の、次世代の方案集への保留を確保し、交叉、突然変異操作による比較的優れた方案への破壊を避けることができる。また、このような方法を無線ネットワーク計画に適用することにより、ネットワークパフォーマンスが比較的優れた無線ネットワーク計画方案を得ることができる。
【実施例５】
【００６１】
本発明の実施例5はさらに多目標最適化装置を提供する。該装置が問題を解決する原理は、実施例1〜3の方法と同様であるため、その具体的な実施は、実施例1〜3の方法の実施を参照することができるので、ここでは、重複記載が省略される。
【００６２】
図6は、本発明の実施例5における多目標最適化装置の構成図である。装置600は、次のようなユニットを含む。
【００６３】
第一生成ユニット601：遺伝的アルゴリズムを用いて、第ｉ世代の方案集に対してランキング、選択、交叉、突然変異を行って、第一方案集を生成し；
第一処理ユニット602：該第一方案集の中の方案と、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とを合併してランキングすることで、該第一方案集の中の方案の優先順位を更新し、該第一方案集の中の方案と同じであるが、方案の優先順位が更新された第二方案集を取得し；
第一確定ユニット603：該第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集に基づいて、第一最適方案集を確定し；
第二処理ユニット604：該第一最適方案集の中の方案を以て該第二方案集の中の方案を置換し、第一所定条件を満足したときに、第i+1世代の方案集を得る。
【００６４】
本実施例から分かるように、遺伝的アルゴリズムに“エリート保留”ポリシーを取り入れ、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の最適方案（エリート）を以て、選択、交叉、突然変異後の第ｉ世代の方案集の中の方案を置換することで、遺伝的アルゴリズムの反復過程における前の幾つかの世代の比較的優れた方案の、次世代の方案集への保留を確保し、交叉、突然変異操作による比較的優れた方案への破壊を避けることができる。
【００６５】
本実施例では、第一生成ユニット601、第一処理ユニット602、第一確定ユニット603、第二処理ユニット604の具体的な実施方式は、実施例1におけるステップ101〜103を参照することができるので、ここではその詳しい説明を省略する。
【００６６】
本実施例では、第一確定ユニット603は、該第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が最高であり且つ第一処理ユニット602により合併、ランキングされた後の優先順位が未変更の方案を、第一最適方案集の中の方案として確定する。
【００６７】
本実施方式から分かるように、第一最適方案集の中の最適方案は、再合併ランキング後に優先順位が依然として最高である方案であるため、このような方案を最適方案とすることにより、選択されたエリートのパフォーマンスが比較的優れたものであるようにさせることができ、例えば、無線ネットワーク計画時に、ネットワークパフォーマンスが比較的優れた計画方案を得ることができる。
【００６８】
本実施例では、図7は本実施例における第二処理ユニット604の構成図である。遺伝的アルゴリズムの反復過程における前の幾つかの世代の最適方案の、第i+1世代の方案集への保留をより一層確保し得るために、第二処理ユニット604は次のようなユニットを含んでも良い。
【００６９】
第一判断ユニット701：第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在するかを判断し；
第一置換ユニット702：第一判断ユニット701の判断結果がはいの場合、該第二方案集の中の方案の優先順位の「低いものから高いものへ」の順序に従って、該第一最適方案集の中の該第二方案集に存在しない第一最適方案を以て、該第二方案集の中の優先順位が最高である方案以外の他の方案を置換し；
第二判断ユニット703：第一判断ユニット701の判断結果がいいえの場合、該第二方案集には優先順位が最高である重複方案が存在するかを判断し；
第二置換ユニット704：第二判断ユニット703の判断結果がはいの場合、該第一最適方案集の中の該第二方案集に存在しない第二最適方案を以て、該第二方案集の中の優先順位が最高である重複方案を置換し；
第三置換ユニット705：第二判断ユニット703の判断結果がいいえの場合、該第一最適方案集の中の該第二方案集に存在しない第三最適方案により、該第二方案集の中の優先順位が最高である方案を置換する。
【００７０】
本実施例では、該第一所定条件は、第一最適方案集には残りの最適方案が存在しないこと、又は、該第二方案集の中の置換され得る方案がすべて置換されたことであり、該第一所定条件を満足したときに、第二処理ユニット604は、置換後に得られた第二方案集を第i+1世代の方案集とする。
【００７１】
本実施例での方案は、無線ネットワーク計画方案であっても良く、また、本実施例における多目標最適化装置は、無線ネットワーク計画に用いられても良い。これにより、ネットワークパフォーマンスが最適である無線ネットワーク計画方案を得ることができる。
【００７２】
図8は、本発明の実施例における多目標最適化装置の他の構成図である。図8に示すように、装置800は、一つのインターフェース（図示せず）、中央処理装置（CPU）820、及び記憶器810を含んでも良い。記憶器810は、中央処理装置820に結合される。そのうち、記憶器810は、各種のデータを記憶することができ、多目標最適化のプログラムを記憶することもでき、また、中央処理装置820の制御により該プログラムを実行することで、各種の所定値などを記憶することもできる。
【００７３】
一実施方式では、多目標最適化の機能は、中央処理装置820に集積することができる。そのうち、中央処理装置820は、遺伝的アルゴリズムを用いて、第ｉ世代の方案集に対してランキング、選択、交叉、突然変異を行って、第一方案集を生成し；該第一方案集の中の方案と、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とを合併してランキングすることで、該第一方案集の中の方案の優先順位を更新し、該第一方案集の中の方案と同じであるが、方案の優先順位が更新された第二方案集を取得し；該第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集に基づいて得られた第一最適方案集の中の方案を以て、該第二方案集の中の方案を置換し、第一所定条件を満足したときに、第i+1世代の方案集を得るように構成されても良い。
【００７４】
そのうち、中央処理装置820はさらに、該第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が最高であり且つ合併、ランキング後の優先順位が未変更である方案を、第一最適方案集の中の方案とするように構成されても良い。
【００７５】
そのうち、中央処理装置820はさらに、該第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在する時に、該第二方案集の中の方案の優先順位の「低いものから高いものへ」の順序に従って、該第一最適方案集の中の該第二方案集に存在しない第一最適方案を用いて、該第二方案集の中の優先順位が最高である方案以外の他の方案を置換し；該第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在せず且つ該第二方案集には優先順位が最高である重複方案が存在する時に、該第一最適方案集の中の該第二方案集に存在しない第二最適方案を用いて、該第二方案集の中の優先順位が最高である重複方案を置換し；該第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在せず且つ該第二方案集には優先順位が最高である重複方案も存在しない時に、該第一最適方案集の中の該第二方案集に存在しない第三最適方案を以て、該第二方案集の中の優先順位が最高である方案を置換するように構成される。
【００７６】
そのうち、中央処理装置820はさらに、該第一最適方案集には残りの最適方案が存在せず、又は、該第二方案集の中の置換され得る方案がすべて置換されたときに、置換後に得られた第二方案集を第i+1世代の方案集とするように構成されても良い。
【００７７】
他の実施方式では、上述の多目標最適化機能を、中央処理装置820に接続されたチップ（図出せず）に構成しても良く、この場合、例えば、中央処理装置820の制御により多目標最適化の機能を実現することができる。
【００７８】
本実施例から分かるように、遺伝的アルゴリズムに“エリート保留”ポリシーを取り入れ、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の最適方案（エリート）を利用して、選択、交叉、突然変異後の第ｉ世代の方案集の中の方案を置換することにより、遺伝的アルゴリズムの反復過程における前の幾つかの世代の比較的優れた方案の、次世代の方案集への保留を確保し、交叉、突然変異操作による比較的優れた方案への破壊を避けることができる。
【実施例６】
【００７９】
本発明の実施例6はさらに無線ネットワーク計画装置を提供する。該装置が問題を解決する原理は、実施例4の方法と同様であるため、その具体的な実施について実施例4の方法の実施を参照することができ、ここでは重複記載が省略される。
【００８０】
図9は無線ネットワーク計画装置の構成図である。装置900は次のようなユニットを含む。
【００８１】
第二生成ユニット901：遺伝的アルゴリズムを用いて、第ｉ世代の無線ネットワーク計画方案集に対してランキング、選択、交叉、突然変異を行って、第一方案集を生成し；
第三処理ユニット902：該第一計画方案集の中の方案と、第0世代から第ｉ世代までの無線ネットワーク計画方案集のうちの１世代又は１世代以上の計画方案集の中の優先順位が高い計画方案とを合併してランキングすることで、該第一計画方案集の中の計画方案の優先順位を更新し、該第一計画方案集の中の計画方案と同じであるが、計画方案の優先順位が更新された第二計画方案集を取得し；
第二確定ユニット903：該第0世代から第ｉ世代までの無線ネットワーク計画方案集のうちの１世代又は１世代以上の計画方案集に基づいて、第一最適化計画方案集を確定し；
第四処理ユニット904：該第一最適化計画方案集の中の計画方案を以て、該第二計画方案集の中の計画方案を置換し、第一所定条件を満足したときに、第i+1世代の無線ネットワーク計画方案集を取得し；
第五処理ユニット905：第二所定条件を満足したときに、該第i+1世代の無線ネットワーク計画方案集を最終無線ネットワーク計画方案集として確定する。
【００８２】
本実施例では、第五処理ユニット905の具体的な実施方式は、実施例4におけるステップ504を参照することができるため、ここではその詳しい説明を省略する。
【００８３】
本実施例では、該装置900はさらに次のようなユニットを含んでも良く、即ち、
初期化ユニット（図示せず）：最初の世代（第0代）の計画方案集（即ち、最初計画方案集）を生成する。
【００８４】
そのうち、該最初計画方案集は、ランダムに生成することができ、例えば、バイナリ符号化方式を採用する場合、ランダムにn個のバイナリ列を生成し、該バイナリ列の長さは、APを配置し得る候補位置の数量に等しくても良い。なお、本実施例はこれに限定されない。
【００８５】
図10は本発明の実施例における無線ネットワーク計画装置の他の構成図である。図10に示すように、装置1000は、一つのインターフェース（図示せず）、中央処理装置（CPU）1020、及び記憶器1010を含んでも良く、記憶器1010は、中央処理装置1020に結合される。そのうち、記憶器1010は、各種のデータを記憶することができ、無線ネットワーク計画のプログラムを記憶することもでき、また、中央処理装置1020の制御の下で該プログラムを実行することで、各種の所定値などを記憶することもできる。
【００８６】
一実施方式では、無線ネットワーク計画の機能は、中央処理装置1020に統合することができる。そのうち、中央処理装置1020は、実施例4における記憶器710に記憶されている多目標最適化プログラムを実行して、第ｉ世代の無線ネットワーク計画方案集に対して処理を行い、第i+1世代の無線ネットワーク計画方案集を取得し、第二所定条件を満足したときに、該第i+1世代の無線ネットワーク計画方案集を最終無線ネットワーク計画方案集として確定するように構成されても良い。
【００８７】
他の実施方式では、上述の無線ネットワーク計画の機能を、中央処理装置1020に接続されるチップ（図未せず）に構成しても良く、この場合、中央処理装置1020の制御により、無線ネットワーク計画の機能を実現することができる。
【００８８】
図10に示すように、装置1000はさらに、入力ユニット1030であって、最初の無線ネットワーク計画方案を入力するためのものと、表示器1040であって、最終確定された無線ネットワーク計画方案などを表示するためのものとを含み、そのうち、これらの部品の機能は、従来技術と同様であるため、ここではその詳しい説明を省略する。なお、装置1000は必ずしも図10に示す全ての部品を含む必要がなく、また、装置1000はさらに図10に示していない他の部品を含んでも良く、これについては従来技術を参照することできる。
【００８９】
上述の実施例から分かるように、遺伝的アルゴリズムに“エリート保留”ポリシーを取り入れ、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の最適方案（エリート）を以て、選択、交叉、突然変異後の第ｉ世代方案集の中の方案を置換することで、遺伝的アルゴリズムの反復過程における前の幾つかの世代の比較的優れた方案の、次世代の方案集への保留を確保し、交叉、突然変異操作による比較的優れた方案への破壊を避けることができる。また、上述の方法を無線ネットワーク計画に適用することにより、ネットワークパフォーマンスが比較的優れた無線ネットワーク計画方案を得ることができる。
【００９０】
本発明の実施例はさらにコンピュータ可読プログラムを提供し、そのうち、多目標最適化装置中で該プログラムを実行する時に、該プログラムは、コンピュータに、該多目標最適化装置中で実施例1〜3の多目標最適化方法を実行させる。
【００９１】
本発明の実施例はさらにコンピュータ可読プログラムを記憶した記憶媒体を提供し、そのうち、該コンピュータ可読プログラムは、コンピュータに、多目標最適化装置中で実施例1〜3の多目標最適化方法を実行させる。
【００９２】
本発明の実施例はさらにコンピュータ可読プログラムを提供し、そのうち、無線ネットワーク計画装置中で該プログラムを実行する時に、該プログラムは、コンピュータに、該無線ネットワーク計画装置中で実施例4の無線ネットワーク計画方法を実行させる。
【００９３】
本発明の実施例はさらにコンピュータ可読プログラムを記憶した記憶媒体を提供し、そのうち、該コンピュータ可読プログラムは、コンピュータに、無線ネットワーク計画装置中で実施例4の無線ネットワーク計画方法を実行させる。
【００９４】
また、本発明の実施例による装置及び方法などは、ソフトウェアにより実現されても良く、ハードウェアにより実現されてもよく、ハードウェア及びソフトウェアの組み合わせにより実現されても良い。また、本発明はこのようなコンピュータ可読プログラムにも関し、即ち、前記プログラムは、ロジック部品により実行されるときに、前記ロジック部品に、上述の装置又は構成要素を実現させることができ、又は、前記ロジック部品に、上述の方法又はそのステップを実現させることができる。さらに、本発明は上述のプログラムを記憶するための記憶媒体、例えば、ハードディスク、磁気ディスク、光ディスク、DVD、フラッシュメモリにも関する。
【００９５】
また、以上の実施例の実施方式に関し、更に以下の付記を開示する。
【００９６】
（付記1）
多目標最適化装置であって、
遺伝的アルゴリズムにより、第ｉ世代の方案集に対してランキング、選択、交叉、突然変異を行って、第一方案集を生成するための第一生成ユニット；
前記第一方案集の中の方案と、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とを合併してランキングすることにより、前記第一方案集の中の方案の優先順位を更新し、前記第一方案集の中の方案と同じであり、且つ方案の優先順位が更新された第二方案集を得るための第一処理ユニット；
前記第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集に基づいて、第一最適方案集を確定するための第一確定ユニット；及び
前記第一最適方案集の中の方案により前記第二方案集の中の方案を置換し、第一所定条件を満足したときに、第i+1世代の方案集を得るための第二処理ユニットを含む、装置。
【００９７】
（付記2）
付記1に記載の装置であって、
前記第一確定ユニットは、前記第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の、優先順位が最高であり且つ前記第一処理ユニットにより合併、ランキングされた後の優先順位が未変更である方案を、第一最適方案集の中の方案と確定する、装置。
【００９８】
（付記3）
付記2に記載の装置であって、
前記第二処理ユニットは、
前記第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在するかを判断するための第一判断ユニット；
前記第一判断ユニットの判断結果が「はい」のときに、前記第二方案集の中の方案の優先順位の「低いものから高いものへ」の順序に従って、前記第一最適方案集の中の前記第二方案集に存在しない第一最適方案により、前記第二方案集の中の優先順位が最高である方案以外の他の方案を置換するための第一置換ユニット；
前記第一判断ユニットの判断結果が「いいえ」のときに、前記第二方案集には優先順位が最高である重複方案が存在するかを判断するための第二判断ユニット；
前記第二判断ユニットの判断結果が「はい」のときに、前記第一最適方案集の中の前記第二方案集に存在しない第二最適方案により、前記第二方案集の中の優先順位が最高である重複方案を置換するための第二置換ユニット；及び
前記第二判断ユニットの判断結果が「いいえ」のときに、前記第一最適方案集の中の前記第二方案集に存在しない第三最適方案により、前記第二方案集の中の優先順位が最高である方案を置換するための第三置換ユニットを含む、装置。
【００９９】
（付記4）
付記1に記載の装置であって、
前記第一所定条件は、前記第一最適方案集に残りの最適方案が存在せず、又は、前記第二方案集の中の置換され得る方案がすべて置換されたということであり、
前記第一所定条件を満足したとき、前記第二処理ユニットは、置換後に得られた第二方案集を第i+1世代の方案集とする、装置。
【０１００】
（付記5）
付記1に記載の装置であって、
前記方案は、無線ネットワーク計画方案である、装置。
【０１０１】
（付記6）
無線ネットワーク計画装置であって、
遺伝的アルゴリズムにより、第ｉ世代の無線ネットワーク計画方案集に対してランキング、選択、交叉、突然変異を行って、第一方案集を生成するための第二生成ユニッ；
前記第一計画方案集の中の方案と、第0世代から第ｉ世代までの無線ネットワーク計画方案集のうちの１世代又は１世代以上の計画方案集の中の優先順位が高い計画方案とを合併してランキングすることにより、前記第一計画方案集の中の計画方案の優先順位を更新し、前記第一計画方案集の中の計画方案と同じであり、且つ計画方案の優先順位が更新された第二計画方案集を得るための第三処理ユニット；
前記第0世代から第ｉ世代までの無線ネットワーク計画方案集のうちの１世代又は１世代以上の計画方案集に基づいて、第一最適化計画方案集を確定するための第二確定ユニット；
前記第一最適化計画方案集の中の計画方案により、前記第二計画方案集の中の計画方案を置換し、第一所定条件を満足したときに、第i+1世代の無線ネットワーク計画方案集を得るための第四処理ユニット；及び
第二所定条件を満足したときに、前記第i+1世代の無線ネットワーク計画方案集を最終無線ネットワーク計画方案集として確定するための第五処理ユニットを含む、装置。
【０１０２】
（付記7）
多目標最適化方法であって、
遺伝的アルゴリズムにより、第ｉ世代の方案集に対してランキング、選択、交叉、突然変異を行って第一方案集を生成し；
前記第一方案集の中の方案と、第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の優先順位が高い方案とを合併してランキングすることにより、前記第一方案集の中の方案の優先順位を更新し、前記第一方案集の中の方案と同じであり、且つ方案の優先順位が更新された第二方案集を取得し；
前記第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集に基づいて得られた第一最適方案集の中の方案により、前記第二方案集の中の方案を置換し、第一所定条件を満足したときに、第i+1世代の方案集を得ることを含む、方法。
【０１０３】
（付記8）
付記7に記載の方法であって、
前記第一最適方案集の中の方案とは、前記第0世代から第ｉ世代までの方案集のうちの１世代又は１世代以上の方案集の中の、優先順位が最高であり且つ合併、ランキング後の優先順位が未変更である方案を指す、方法。
【０１０４】
（付記9）
付記8に記載の方法であって、
前記第一最適方案集の中の方案により前記第二方案集の中の方案を置換することは、
前記第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在するときに、前記第二方案集の中の方案の優先順位の「低いものから高いものへ」の順序に従って、前記第一最適方案集の中の前記第二方案集に存在しない第一最適方案により、前記第二方案集の中の優先順位が最高である方案以外の他の方案を置換し；
前記第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在せず且つ前記第二方案集には優先順位が最高である重複方案が存在するときに、前記第一最適方案集の中の前記第二方案集に存在しない第二最適方案により、前記第二方案集の中の優先順位が最高である重複方案を置換し；及び
前記第二方案集には優先順位が最高である方案以外の他の低い優先順位の方案が存在せず且つ前記第二方案集には優先順位が最高である重複方案も存在しないときに、前記第一最適方案集の中の前記第二方案集に存在しない第三最適方案により、前記第二方案集の中の優先順位が最高である方案を置換することを含む、方法。
【０１０５】
（付記10）
付記7に記載の方法であって、
第一所定条件を満足したときに、第i+1世代の方案集を得ることは、
前記第一最適方案集には残りの最適方案が存在せず、又は、前記第二方案集の中の置換され得る方案がすべて置換されたときに、置換後に得られた第二方案集を第i+1世代の方案集とすることを含む、方法。
【０１０６】
以上、本発明の好ましい実施形態を説明したが、本発明はこの実施形態に限定されず、本発明の趣旨を離脱しない限り、本発明に対するあらゆる変更は本発明の技術的範囲に属する。
【図１】
0006724576.tif 000002
【図２】
0006724576.tif 000003
【図３】
0006724576.tif 000004
【図４】
0006724576.tif 000005
【図５】
0006724576.tif 000006
【図６】
0006724576.tif 000007
【図７】
0006724576.tif 000008
【図８】
0006724576.tif 000009
【図９】
0006724576.tif 000010
【図１０】
0006724576.tif 000011