論文の概要: Rethinking Selection in Generational Genetic Algorithms to Solve Combinatorial Optimization Problems: An Upper Bound-based Parent Selection Strategy for Recombination
- arxiv url: http://arxiv.org/abs/2410.03863v1
- Date: Fri, 4 Oct 2024 18:56:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-02 15:40:54.513036
- Title: Rethinking Selection in Generational Genetic Algorithms to Solve Combinatorial Optimization Problems: An Upper Bound-based Parent Selection Strategy for Recombination
- Title(参考訳): 世代別遺伝的アルゴリズムの選択再考による組合せ最適化問題の解法--組換えのための上界に基づく親選択戦略
- Authors: Prashant Sankaran, Katie McConky,
- Abstract要約: 本研究は、アッパーバウンドベース親選択(UBS)と呼ばれる世代GA設定における組換え決定論的親選択戦略を提案する。
具体的には、UBS戦略の一環として、MABフレームワークと修正 UCB1アルゴリズムを用いて親選択問題を定式化し、探索と利用を管理する。
従来の選択戦略と比較してUBSの有効性を示すため,チームオリエンテーリングと2次割り当ての2つのNPハード最適化問題について検討した。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Existing stochastic selection strategies for parent selection in generational GA help build genetic diversity and sustain exploration; however, it ignores the possibility of exploiting knowledge gained by the process to make informed decisions for parent selection, which can often lead to an inefficient search for large, challenging optimization problems. This work proposes a deterministic parent selection strategy for recombination in a generational GA setting called Upper Bound-based Parent Selection (UBS) to solve NP-hard combinatorial optimization problems. Specifically, as part of the UBS strategy, we formulate the parent selection problem using the MAB framework and a modified UCB1 algorithm to manage exploration and exploitation. Further, we provided a unique similarity-based approach for transferring knowledge of the search progress between generations to accelerate the search. To demonstrate the effectiveness of the proposed UBS strategy in comparison to traditional stochastic selection strategies, we conduct experimental studies on two NP-hard combinatorial optimization problems: team orienteering and quadratic assignment. Specifically, we first perform a characterization study to determine the potential of UBS and the best configuration for all the selection strategies involved. Next, we run experiments using these best configurations as part of the comparison study. The results from the characterization studies reveal that UBS, in most cases, favors larger variations among the population between generations. Next, the comparison studies reveal that UBS can effectively search for high-quality solutions faster than traditional stochastic selection strategies on challenging NP-hard combinatorial optimization problems under given experimental conditions.
- Abstract(参考訳): 世代別GAにおける親選択の確率的選択戦略は遺伝的多様性の構築と探索の維持に役立つが、親選択のための情報的決定を行うプロセスによって得られる知識を活用する可能性を無視しており、多くの場合、大きな、挑戦的な最適化問題の非効率な探索につながる。
本研究では, NP-ハード組合せ最適化問題を解くために, アッパーバウンドに基づくペアレント選択 (UBS) と呼ばれる世代GA設定において, リコンビネーションのための決定論的親選択戦略を提案する。
具体的には、UBS戦略の一環として、MABフレームワークと修正 UCB1アルゴリズムを用いて親選択問題を定式化し、探索と利用を管理する。
さらに,検索の進歩に関する知識を世代間で伝達し,検索を高速化する,ユニークな類似性に基づくアプローチを提案する。
従来の確率的選択戦略と比較して,提案手法の有効性を示すため,チームオリエンテーリングと2次割り当ての2つのNPハード組合せ最適化問題を実験的に検討した。
具体的には、まず、UBSの可能性と、関連するすべての選択戦略に最適な構成を決定するために、キャラクタリゼーション研究を行う。
次に、これらの最適構成を用いた実験を比較研究の一環として実施する。
評価研究の結果、ほとんどの場合、UBSは世代間での個体数に大きなバリエーションを好んでいることが明らかとなった。
次に, 実験条件下でのNP-ハード組合せ最適化問題に対して, UBSは従来の確率的選択法よりも高速に, 高品質な解を探索できることを示した。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳(メタデータ) (2024-11-07T17:05:31Z) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳(メタデータ) (2024-06-21T05:57:08Z) - Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳(メタデータ) (2024-06-05T22:52:27Z) - Genetic Engineering Algorithm (GEA): An Efficient Metaheuristic
Algorithm for Solving Combinatorial Optimization Problems [1.8434042562191815]
遺伝的アルゴリズム(GA)は最適化問題の解法における効率性で知られている。
本稿では遺伝子工学の概念からインスピレーションを得るため,遺伝子工学アルゴリズム(GEA)と呼ばれる新しいメタヒューリスティックアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-28T13:05:30Z) - Improved Solution Search Performance of Constrained MOEA/D Hybridizing
Directional Mating and Local Mating [0.0]
直接交配方法は、第1の親が選択された後、目的空間の最適方向に沿って他方の親を選択する。
第1親からの最適方向が支配するより良い解が欠如しているため、生成が進むにつれて直接交配が困難になる。
そこで本研究では,親の近辺から親を選択するために,局所的交配を用いたハイブリッド手法を提案する。
論文 参考訳(メタデータ) (2023-07-24T15:32:53Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳(メタデータ) (2023-07-01T18:35:21Z) - A Reinforcement Learning-assisted Genetic Programming Algorithm for Team
Formation Problem Considering Person-Job Matching [70.28786574064694]
解の質を高めるために強化学習支援遺伝的プログラミングアルゴリズム(RL-GP)を提案する。
効率的な学習を通じて得られる超ヒューリスティックなルールは、プロジェクトチームを形成する際の意思決定支援として利用することができる。
論文 参考訳(メタデータ) (2023-04-08T14:32:12Z) - Simulation-guided Beam Search for Neural Combinatorial Optimization [13.072343634530883]
ニューラル最適化問題に対するシミュレーション誘導ビームサーチ(SGBS)を提案する。
我々は、SGBSと効率的なアクティブサーチ(EAS)を併用し、SGBSはEASでバックプロパゲーションされたソリューションの品質を高める。
提案手法をよく知られたCOベンチマークで評価し,SGBSが合理的な仮定で得られた解の質を著しく向上することを示す。
論文 参考訳(メタデータ) (2022-07-13T13:34:35Z) - Best Subset Selection with Efficient Primal-Dual Algorithm [24.568094642425837]
多くの学習問題に対するベストサブセット選択は「ゴールドスタンダード」と見なされている。
本稿では,$ell$-regularized問題系の二重形式について検討する。
主問題構造と双対問題構造に基づく効率的な主対法が開発されている。
論文 参考訳(メタデータ) (2022-07-05T14:07:52Z) - VNE Strategy based on Chaotic Hybrid Flower Pollination Algorithm
Considering Multi-criteria Decision Making [12.361459296815559]
仮想ネットワーク埋め込み (Virtual Network Embedding, VNE) 問題に対するハイブリッド花の受粉アルゴリズムの設計戦略について論じる。
クロス操作は、グローバル検索を完了させるためにクロスポリン化操作を置き換えるために使用される。
従来のフィットネスベースの選択戦略の補完としてライフサイクルメカニズムが導入されている。
論文 参考訳(メタデータ) (2022-02-07T00:57:00Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳(メタデータ) (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。