問題タブ [genetic-algorithm]

巡回セールスマン問題 (TSP) を解決するために遺伝的アルゴリズムを実装しました。ミューテーションのみを使用すると、クロスオーバーを追加する場合よりも優れたソリューションが見つかります。通常のクロスオーバー メソッドが TSP で機能しないことはわかっているので、Ordered Crossover メソッドとPMX Crossoverメソッドの両方を実装しましたが、どちらも悪い結果に悩まされました。

私が使用している他のパラメータは次のとおりです。

変異: シングル スワップ変異または反転サブシーケンス変異 (ここで Tiendil が説明したように) で、変異率は 1% から 25% の間でテストされています。

選択: ルーレット盤の選択

フィットネス関数: 1 / ツアーの距離

母集団のサイズ: 100、200、500 をテストしました。GA も 5 回実行して、さまざまな開始母集団を用意しました。

停止条件：2500世代

同じ 26 ポイントのデータセットを使用すると、突然変異率の高い純粋な突然変異を使用して、通常、約 500 ～ 600 距離の結果が得られます。クロスオーバーを追加すると、結果は通常 800 距離の範囲になります。もう1つの紛らわしいことは、問題を解決するために非常に単純な山登りアルゴリズムも実装したことです.1000回実行すると（GAを5回実行するよりも高速です）、約410〜450の距離で結果が得られます. GAを使用してより良い結果を得るために。

クロスオーバーを追加すると GA のパフォーマンスが低下する理由について何か考えはありますか? そして、ローカル最大値を見つけたら探索する方法がないため、ローカル最大値に固執する単純なヒルクライムアルゴリズムよりもパフォーマンスがはるかに悪いのはなぜですか?

I'm making a Genetic Program, but I'm hitting a limitation with C# where I want to present new functions to the algorithm but I can't do it without recompiling the program. In essence I want the user of the program to provide the allowed functions and the GP will automatically use them. It would be great if the user is required to know as little about programming as possible.

I want to plug in the new functions without compiling them into the program. In Python this is easy, since it's all interpreted, but I have no clue how to do it with C#. Does anybody know how to achieve this in C#? Are there any libraries, techniques, etc?

私はソフトウェアテストで自分のプロジェクトを行っています。遺伝的アルゴリズムは、MATLAB で自動テスト データ\テスト ケースを生成するために使用したい手法です。

私のプロジェクトを成功させるために私を助けてください。

私はこれについてさまざまなものを読み、関連する原理と概念を理解していますが、直接接続されていない隣接する都市 (染色体内) を含む染色体 (ルートを表す) の適合度を計算する方法の詳細について言及している論文はありません。 (グラフ内の) エッジによって。

たとえば、各遺伝子がグラフ/マップ上の都市のインデックスを表す染色体 1|3|2|8|4|5|6|7 が与えられた場合、その適合度 (つまり、たとえば、都市 2 と 8 の間に直接のエッジ/リンクがない場合。2 と 8 の間のルートを計算し、このルートの距離を合計に追加するために、ある種の貪欲なアルゴリズムに従いますか?

この問題は、GA を TSP に適用する場合によく見られます。やったことがある方、感想を教えてください。ありがとう。

標準のオフライン学習ではなくオンライン学習で実装されたGPを見た人はいますか？私は遺伝子プログラムでいくつかのことをしました、そして私は単に学習プロセスをオンラインにするための良い方法が何であるかを理解することができません。

何かアイデアがあったり、実装を見たり、私が見ることができる参考資料があれば教えてください。

遺伝的アルゴリズムや蟻コロニー最適化などを使用してTSPを解決する方法について、いくつかの記事とサンプルコードを読みました。しかし、見つけたものにはすべて、時間（ウィンドウ）の制約が含まれていませんでした。「私は午前12時前に顧客xにいる必要があります）」そして対称性を仮定しました。

TSPに制約を追加する方法と、それらをコードで表現する方法を説明するサンプルコードまたは記事の方向性を誰かに教えてもらえますか。

ありがとう！

プログラミングが難しい問題のあるスケジューリングプログラムを書いています。いくつかのイベントがあり、それぞれに複数の会議時間があります。各イベントの複数の会議時間の1つを使用して、各スケジュールに特定のイベントが1回だけ含まれるように、会議時間の配置を見つける必要があります。

明らかにブルートフォースを使用することはできますが、それが最善の解決策になることはめったにありません。これは比較的基本的なコンピュータサイエンスの問題だと思います。コンピュータサイエンスのクラスを受講できるようになったら、この問題について学びます。それまでの間、これについて読むことができるリンク、またはGoogleで検索できる名前をお勧めします。

私にはそれぞれ試験を受けNなければならない人がいます。T各試験には「ある程度の」時間がかかります (例: 30 分) (早期に終了することはありません)。試験は、試験官の前で実施する必要があります。

私は各人が全体の時間内に試験官の前で各試験を受けるようにスケジュールする必要がありますが、昼休みを避け、最小数の試験官を最小限の時間使用します (つまり、アイドル状態の試験官がいない/最小)。

次の制限があります。

• 人は一度に 2 つの場所にいることはできません
• 1 人 1 人が各試験を 1 回受ける必要があります
• 誰も同じ検査官によって二度検査されるべきではない

最適なソリューションはおそらく NP-Complete であり、遺伝的アルゴリズムを使用して最良の推定値を取得するのがおそらく最善であることを認識しています (これに似ていますか?座席計画ソフトウェアの推奨事項 (そのような獣は存在しますか?) )。

私は遺伝的アルゴリズムの仕組みに満足しています.私が苦労しているのは、パラメーターを遺伝的に操作できるようにプログラムで問題をモデル化する方法です..

各試験に同じ時間がかかった場合、時間をこれらの長さに分割し、時間枠と試験官のマトリックスを作成して、受験者をドロップします。ただし、各試験の時間は必ずしも同じ、私はこれにアプローチする方法について少し迷っています。

現在これをやっています：

• すべての受験者と試験の間で、実施する必要があるすべての「テスト」のリストを作成します
• テストがあるのと同じ数の試験官から始める
• すべての試験官を繰り返しループします。それぞれの試験官について: (制限に基づいて) 試験官に適格な予定外の試験を見つけます。
• スケジュール可能なすべてのテストが終了するまで続行します。
• 予定外のテストがある場合は、試験官の数を増やして、もう一度開始します。

現在はかなり粗雑に感じられるため、これにアプローチする方法についてより良い提案を探しています。

私は大学で少し GP (注: ごくわずか) の仕事をしましたが、最近それをいじっています。私の質問は、最初の実行設定に関するものです (人口サイズ、世代数、木の最小/最大深さ、初期木の最小/最大深さ、さまざまな再生操作に使用するパーセンテージなど)。これらのパラメータを設定する通常の方法は何ですか? 人々はどのような論文やサイトを参考にしていますか?

私は整数線形計画法の初心者です。組み合わせ最適化問題を解くために整数線形計画法ソルバーを使用する予定です。IDE での C++/オブジェクト指向プログラミングに精通しています。現在、ほとんどの場合、Cygwin で NetBeans を使用してアプリケーションを作成しています。

簡単に使用できる ILP ソルバーがあるかどうか尋ねてもよろしいですか? または、解決したい問題によって異なりますか？リソース マッピングの最適化を試みています。さらに情報が必要な場合はお知らせください。

どうもありがとう、キャシー。