遺伝的アルゴリズムは、進化と同じやり方で候補解の集団を改良します。適応度の高い親を選び、組み合わせ、ランダムな突然変異を加えます。ここでは候補はビット列で、適応度は 1 の個数です (OneMax 問題)。
テストできるように、ランダムな選択はすべて与えられます。N 本の文字列 (N は偶数) から、ペアごとに N 個の子を作ります。ペア k = 0, 1, …, N/2 - 1 について:
- 選択: parent1 はトーナメント
tournaments[2k]の勝者、parent2 はtournaments[2k + 1]の勝者です。トーナメント[i, j]はpopulation[i]とpopulation[j]のうち 1 の多い方が勝ち、同数ならpopulation[i]が勝ちます。 - 交叉 (c =
crossover_points[k]): 子 2k = parent1[0:c] + parent2[c:]、子 2k + 1 = parent2[0:c] + parent1[c:]。
その後、各突然変異 [child, position] を順に適用し、その子のそのビットを反転します。
ga_generation(population, tournaments, crossover_points, mutations) を実装してください。
入力
population: 長さ L の N 本のビット列。
tournaments: 集団のインデックスの N 個のペア。
crossover_points: N/2 個の切断点。それぞれ 1 以上 L - 1 以下。
mutations: [child, position] のペア (空の場合もあります)。
出力
N 個の子を順に返します。
制約
2 ≤ N ≤ 200 (N は偶数)、2 ≤ L ≤ 64
0 ≤ 突然変異の数 ≤ 1,000
例
入力：
population = ["0000", "1111", "1100", "0011"]
tournaments = [
[0, 1],
[2, 3],
[1, 2],
[0, 3]
]
crossover_points = [2, 1]
mutations = [
[0, 0]
]
期待される出力：
["0100", "1111", "1011", "0111"]解説
ペア 0: "1111" が "0000" に勝ち、"1100" と "0011" は同数なので前者が勝ちます。2 ビット目の後で切ると "1100" と "1111"。ペア 1: 親は "1111" と "0011"、1 ビット目の後で切ると "1011" と "0111"。最後に子 0 のビット 0 を反転して "0100"。
入力：
population = ["10", "01"]
tournaments = [
[0, 1],
[1, 0]
]
crossover_points = [1]
mutations = []
期待される出力：
["11", "00"]解説
両方とも 1 が 1 つなので、各トーナメントは最初のインデックスが勝ちます: parent1 = "10"、parent2 = "01"。1 ビット目の後で切ると "11" と "00"。
参考資料
-
例 1 未実行入力：
population = ["0000", "1111", "1100", "0011"] tournaments = [ [0, 1], [2, 3], [1, 2], [0, 3] ] crossover_points = [2, 1] mutations = [ [0, 0] ]期待される出力：["0100", "1111", "1011", "0111"]あなたの出力 -
例 2 未実行入力：
population = ["10", "01"] tournaments = [ [0, 1], [1, 0] ] crossover_points = [1] mutations = []期待される出力：["11", "00"]あなたの出力
提出時に非公開テスト4件も実行されます。 失敗したテストがあれば、そのテストが表示されます。チャレンジを解くとすべて見られます。
Online Java Compiler
Write, compile, run, and debug Java code online in a full-featured browser IDE. Work with multiple files, save your workspace, and share or collaborate in real time - no setup required.
☕ このJavaオンライン実行ツールについて
CodeUtility Java Executorは、ブラウザ上で直接Javaプログラムを記述・実行できるツールです - インストールやJDKの設定、IDEは不要です。安全なサンドボックス上で動作し、実際のJavaランタイム バージョン8、11、17、21、そして最新に対応しています。
このツールは、本物のjavacコンパイラとJavaランタイム環境をクラウドで使用してコードをコンパイル・実行します。
そのため、クラスやメソッド、ロジックをローカルとまったく同じ挙動でテストできます。
オブジェクト指向の練習、面接対策、統合前のスニペット検証など、あらゆる用途で CodeUtility Java Executorは高速かつ信頼できる実行環境を提供し、どんなデバイスからでもすぐに本物のJavaコードを実行できます。
同じ実行環境で、複数ファイル対応エディター、分離された実行ターミナル、ランタイム別ライブラリ、永続ワークスペース、共有、リアルタイム共同作業を利用できます。
この実行環境の使い方
ランタイムを選択し、ファイルを開くか作成してコードを記述し、［実行］を選択します。出力はターミナルに表示されます。サインインしたユーザーは、ワークスペースにファイルを保存し、ライブラリをインストールして、共有を通じて共同作業できます。
- バージョンを選択して現在のファイルを編集するか、ワークスペース内の別のファイルを開きます。
- コードを実行し、求められた場合はターミナルに入力して、保存された実行履歴を確認します。
- 複数のコードスニペットが必要な作業では、ライブラリ、ワークスペースツール、共有、チャットを利用します。
💡 上のエディタで試せるJavaの基本とサンプル
1. 変数と定数の宣言
Javaでは各変数の型を宣言する必要があります。定数にはfinalを使います。
int age = 30;
double pi = 3.14159;
char grade = 'A';
String name = "Alice";
boolean isActive = true;
// 定数
final int MAX_USERS = 100;
final String COMPANY = "CodeUtility";2. 条件分岐（if / switch）
制御フローにはif、else if、switchを使います。
int x = 2;
if (x == 1) {
System.out.println("1");
} else if (x == 2) {
System.out.println("2");
} else {
System.out.println("その他");
}
switch (x) {
case 1:
System.out.println("1");
break;
case 2:
System.out.println("2");
break;
default:
System.out.println("その他");
}3. ループ
繰り返しにはfor、while、do-whileを使います。
for (int i = 0; i < 3; i++) {
System.out.println(i);
}
int n = 3;
while (n > 0) {
System.out.println(n);
n--;
}4. 配列
配列は同じ型の要素を固定長で保持します。
int[] numbers = {10, 20, 30};
System.out.println(numbers[1]);5. ArrayListの操作
ArrayListは可変長のリストに使います。
import java.util.ArrayList;
ArrayList<Integer> nums = new ArrayList<>();
nums.add(1);
nums.add(2);
nums.add(3);
nums.remove(Integer.valueOf(2));
for (int num : nums) {
System.out.print(num + " ");
}6. コンソール入出力
入力にはScanner、出力にはSystem.outを使います。
import java.util.Scanner;
Scanner scanner = new Scanner(System.in);
System.out.print("お名前を入力してください: ");
String name = scanner.nextLine();
System.out.println("こんにちは、" + name);7. メソッド
戻り値の型と引数を指定してメソッドを定義します。
public static int add(int a, int b) {
return a + b;
}
System.out.println(add(3, 4));8. HashMap
HashMapはキーと値のペアを格納するために使います。
import java.util.HashMap;
HashMap<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30);
System.out.println(ages.get("Alice"));9. 例外処理
実行時例外はtryとcatchで処理します。
try {
throw new Exception("問題が発生しました");
} catch (Exception e) {
System.out.println(e.getMessage());
}10. ファイル入出力
ファイル操作にはjava.nio.fileのFilesとPathsを使います。
import java.nio.file.*;
import java.io.IOException;
Files.writeString(Paths.get("file.txt"), "こんにちは、ファイル");
String content = Files.readString(Paths.get("file.txt"));
System.out.println(content);11. 文字列操作
Javaの文字列はlength()、substring()、contains()など多くのメソッドをサポートします。
String text = "Hello World";
System.out.println(text.length());
System.out.println(text.substring(0, 5));
System.out.println(text.contains("World"));12. クラスとオブジェクト
Javaはクラスとインスタンスを用いたオブジェクト指向プログラミングをサポートします。
class Person {
String name;
Person(String name) {
this.name = name;
}
void greet() {
System.out.println("こんにちは、私は " + name);
}
}
Person p = new Person("Alice");
p.greet();