論文の概要: A Non-Dominated Sorting Based Customized Random-Key Genetic Algorithm
for the Bi-Objective Traveling Thief Problem
- arxiv url: http://arxiv.org/abs/2002.04303v3
- Date: Tue, 28 Jul 2020 11:41:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 01:45:50.326124
- Title: A Non-Dominated Sorting Based Customized Random-Key Genetic Algorithm
for the Bi-Objective Traveling Thief Problem
- Title（参考訳）: 非支配的ソーティングに基づく二目的走行肉問題のためのカスタマイズランダムキー遺伝的アルゴリズム
- Authors: Jonatas B. C. Chagas and Julian Blank and Markus Wagner and Marcone J.
F. Souza and Kalyanmoy Deb
- Abstract要約: 本稿では,よく研究されたトラベリングティーフ問題 (TTP) の2目的変種を解く方法を提案する。
BI-TTPは、旅行時間全体の最小化と、収集したアイテムの利益の最大化を目的としている。
提案手法は,問題固有の特徴をカスタマイズしたバイアスランダム鍵遺伝的アルゴリズムに基づく。
- 参考スコア（独自算出の注目度）: 7.088487500434561
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a method to solve a bi-objective variant of the
well-studied Traveling Thief Problem (TTP). The TTP is a multi-component
problem that combines two classic combinatorial problems: Traveling Salesman
Problem (TSP) and Knapsack Problem (KP). We address the BI-TTP, a bi-objective
version of the TTP, where the goal is to minimize the overall traveling time
and to maximize the profit of the collected items. Our proposed method is based
on a biased-random key genetic algorithm with customizations addressing
problem-specific characteristics. We incorporate domain knowledge through a
combination of near-optimal solutions of each subproblem in the initial
population and use a custom repair operator to avoid the evaluation of
infeasible solutions. The bi-objective aspect of the problem is addressed
through an elite population extracted based on the non-dominated rank and
crowding distance. Furthermore, we provide a comprehensive study showing the
influence of each parameter on the performance. Finally, we discuss the results
of the BI-TTP competitions at EMO-2019 and GECCO-2019 conferences where our
method has won first and second places, respectively, thus proving its ability
to find high-quality solutions consistently.
- Abstract（参考訳）: 本稿では,よく研究されたトラベリングティーフ問題 (TTP) の2目的変異を解く方法を提案する。
TTPは、トラベリングセールスマン問題(TSP)とクナプサック問題(KP)の2つの古典的な組合せ問題を組み合わせた多成分問題である。
BI-TTP(BI-TTP)は,TTPの2目的バージョンであり,総走行時間を最小化し,収集したアイテムの利益を最大化する。
提案手法は,問題固有の特徴をカスタマイズしたバイアスランダム鍵遺伝的アルゴリズムに基づく。
初期個体群における各サブプロブレムの近最適解の組み合わせによりドメイン知識を取り入れ, 適用不可能解の評価を避けるために, カスタム修復演算子を用いる。
この問題の両目的的側面は、非支配階級と群集距離に基づいて抽出されたエリート集団を通して解決される。
さらに,各パラメータが性能に与える影響を包括的に検討した。
最後に,提案手法がそれぞれ第1位,第2位を獲得したEMO-2019およびGECCO-2019のBI-TTPコンペティションの結果について述べる。
関連論文リスト
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Addressing The Knapsack Challenge Through Cultural Algorithm
Optimization [0.0]
我々は,0-1knapsack問題の解法に特化して設計された,新しい文化アルゴリズムの変種を紹介する。
提案アルゴリズムは,集団を改良するための信念空間と,交叉率と突然変異率を動的に調節する2つの重要な機能を導入している。
我々は,このアルゴリズムがグローバルな最適点を一貫して見つけ出す上で,顕著な効率性を示す証拠を提供する。
論文 参考訳（メタデータ） (2023-10-30T17:05:19Z) - Active Ranking of Experts Based on their Performances in Many Tasks [72.96112117037465]
我々は、dタスクのパフォーマンスに基づいて、n名のエキスパートをランク付けする問題を考察する。
我々は,各専門家のペアに対して,各タスクにおいて他方よりも優れているという,単調な仮定を定めている。
論文 参考訳（メタデータ） (2023-06-05T06:55:39Z) - Communication-Efficient Federated Bilevel Optimization with Local and
Global Lower Level Problems [118.00379425831566]
我々はFedBiOAccという通信効率の高いアルゴリズムを提案する。
我々は、FedBiOAcc-Localがこの種の問題に対して同じ速度で収束していることを証明する。
実験結果から,アルゴリズムの性能が向上した。
論文 参考訳（メタデータ） (2023-02-13T21:28:53Z) - A Novel Approach for Auto-Formulation of Optimization Problems [66.94228200699997]
Natural Language for Optimization (NL4Opt) NeurIPS 2022コンペティションでは、最適化ソルバのアクセシビリティとユーザビリティの改善に重点を置いている。
本稿では,チームのソリューションについて述べる。
提案手法は,サブタスク1のF1スコアとサブタスク2の0.867の精度を達成し,それぞれ第4位,第3位を獲得した。
論文 参考訳（メタデータ） (2023-02-09T13:57:06Z) - MAP-Elites based Hyper-Heuristic for the Resource Constrained Project
Scheduling Problem [0.3359875577705538]
資源制約型プロジェクトスケジューリング問題(RCPSP)はNP-Hard最適化問題である。
本稿では, MAP-Elites を用いたハイパーヒューリスティック (MEHH) を用いて, RCPSP の効率的な優先ルールの自動発見を行う。
論文 参考訳（メタデータ） (2022-04-24T01:49:59Z) - On the Use of Quality Diversity Algorithms for The Traveling Thief
Problem [11.590506672325668]
現実世界の最適化では、いくつかのサブプロブレムが相互作用し、主要な問題を形成するのが一般的である。
本稿では,旅行セールスパーソン問題(TSP)とクナップサック問題(KP)の相互依存性を品質多様性(QD)アプローチを用いて検討する。
論文 参考訳（メタデータ） (2021-12-16T05:08:39Z) - Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep
Unrolling [86.85697555068168]
2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。
特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。
PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
論文 参考訳（メタデータ） (2021-05-05T03:36:00Z) - Breeding Diverse Packings for the Knapsack Problem by Means of
Diversity-Tailored Evolutionary Algorithms [13.026567958569965]
我々はknapsack問題(KP)に対する進化的多様性の最適化について研究する。
我々のゴールは、KP のよく知られた FPTAS によって計算された初期近似解で、すべての利益が少なくとも$(mu+1)$-EA である解の集団を進化させることである。
論文 参考訳（メタデータ） (2021-04-27T12:26:18Z) - Solving the Travelling Thief Problem based on Item Selection Weight and
Reverse Order Allocation [8.620967398331265]
旅行泥棒問題(TTP)は多くの学者を引き付ける挑戦的な最適化問題です。
本論文では,TTPを理論的および実証的に検討する。
提案した選択項目と逆順序のソート項目の定式化によって算出されたスコア値に基づくアルゴリズムを提案し,この問題を解く。
論文 参考訳（メタデータ） (2020-12-16T12:06:05Z) - Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
i) 任意の状態空間, (ii) 任意の行動空間, (iii) 任意の送信者のユーティリティ関数を用いて, 一般の状況下での公衆の説得問題を考察する。
任意の公的な説得問題に対して準多項式時間ビクテリア近似アルゴリズムを提案し、特定の設定でQPTASを出力する。
論文 参考訳（メタデータ） (2020-02-12T18:59:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。