google-research

1
// Copyright 2024 The Google Research Authors.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14

15
#include "mutator.h"
16

17
#include <memory>
18
#include <random>
19

20
#include "definitions.h"
21
#include "instruction.pb.h"
22
#include "algorithm.h"
23
#include "algorithm_test_util.h"
24
#include "generator.h"
25
#include "generator_test_util.h"
26
#include "mutator.pb.h"
27
#include "random_generator.h"
28
#include "test_util.h"
29
#include "gtest/gtest.h"
30

31
namespace automl_zero {
32

33
using ::std::function;  // NOLINT
34
using ::std::make_shared;  // NOLINT
35
using ::std::mt19937;  // NOLINT
36
using ::std::shared_ptr;  // NOLINT
37
using ::std::vector;  // NOLINT
38
using ::testing::Test;
39

40
TEST(MutatorTest, Runs) {
41
  mt19937 bit_gen;
42
  RandomGenerator rand_gen(&bit_gen);
43
  Mutator mutator(
44
      ParseTextFormat<MutationTypeList>(
45
          "mutation_types: [ "
46
          "  ALTER_PARAM_MUTATION_TYPE, "
47
          "  RANDOMIZE_INSTRUCTION_MUTATION_TYPE, "
48
          "  RANDOMIZE_COMPONENT_FUNCTION_MUTATION_TYPE, "
49
          "  INSERT_INSTRUCTION_MUTATION_TYPE, "
50
          "  TRADE_INSTRUCTION_MUTATION_TYPE, "
51
          "  REMOVE_INSTRUCTION_MUTATION_TYPE "
52
          "] "),
53
      0.5,  // mutate_prob
54
      {NO_OP, SCALAR_SUM_OP, VECTOR_SUM_OP},  // allowed_setup_ops
55
      {NO_OP, SCALAR_DIFF_OP, VECTOR_DIFF_OP},  // allowed_predict_ops
56
      {NO_OP, SCALAR_PRODUCT_OP, VECTOR_PRODUCT_OP},  // allowed_learn_ops
57
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
58
      &bit_gen,
59
      &rand_gen);
60
  Generator generator(NO_OP_ALGORITHM, 10, 10, 10, {}, {}, {}, nullptr,
61
                      nullptr);
62
  shared_ptr<const Algorithm> algorithm =
63
      make_shared<const Algorithm>(SimpleRandomAlgorithm());
64
  mutator.Mutate(&algorithm);
65
}
66

67
TEST(MutatorTest, CoversActions) {
68
  mt19937 bit_gen;
69
  RandomGenerator rand_gen(&bit_gen);
70
  Mutator mutator(
71
      ParseTextFormat<MutationTypeList>(
72
          "mutation_types: [ "
73
          "  INSERT_INSTRUCTION_MUTATION_TYPE, "
74
          "  TRADE_INSTRUCTION_MUTATION_TYPE, "
75
          "  REMOVE_INSTRUCTION_MUTATION_TYPE "
76
          "] "),
77
      1.0,  // mutate_prob
78
      {},  // allowed_setup_ops
79
      {NO_OP},  // allowed_predict_ops
80
      {},  // allowed_learn_ops
81
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
82
      &bit_gen,
83
      &rand_gen);
84
  const Algorithm algorithm = SimpleRandomAlgorithm();
85
  const IntegerT original_size = algorithm.predict_.size();
86
  EXPECT_TRUE(IsEventually(
87
      function<IntegerT(void)>([&](){
88
        auto mutated_algorithm = make_shared<const Algorithm>(algorithm);
89
        mutator.Mutate(&mutated_algorithm);
90
        return static_cast<IntegerT>(mutated_algorithm->predict_.size());
91
      }),
92
      {original_size - 1, original_size, original_size + 1},
93
      {original_size - 1, original_size, original_size + 1}));
94
}
95

96
TEST(MutatorTest, RespectsMutateProb) {
97
  mt19937 bit_gen;
98
  RandomGenerator rand_gen(&bit_gen);
99
  Mutator mutator(
100
      ParseTextFormat<MutationTypeList>(
101
          "mutation_types: [ "
102
          "  INSERT_INSTRUCTION_MUTATION_TYPE "
103
          "] "),
104
      0.5,  // mutate_prob
105
      {},  // allowed_setup_ops
106
      {NO_OP},  // allowed_predict_ops
107
      {},  // allowed_learn_ops
108
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
109
      &bit_gen,
110
      &rand_gen);
111
  const Algorithm algorithm = SimpleRandomAlgorithm();
112
  const IntegerT original_size = algorithm.predict_.size();
113
  EXPECT_TRUE(IsEventually(
114
      function<IntegerT(void)>([&](){
115
        auto mutated_algorithm = make_shared<const Algorithm>(algorithm);
116
        mutator.Mutate(&mutated_algorithm);
117
        return static_cast<IntegerT>(mutated_algorithm->predict_.size());
118
      }),
119
      {original_size, original_size + 1},
120
      {original_size, original_size + 1}));
121
}
122

123
TEST(MutatorTest, InstructionIndexTest) {
124
  mt19937 bit_gen;
125
  RandomGenerator rand_gen(&bit_gen);
126
  Mutator mutator(
127
      MutationTypeList(), 0.0, {}, {}, {},
128
      0, 10000, 0, 10000, 0, 10000,
129
      &bit_gen, &rand_gen);
130
  EXPECT_TRUE(IsEventually(
131
      function<InstructionIndexT(void)>(
132
          [&](){return mutator.InstructionIndex(5);}),
133
      Range<InstructionIndexT>(0, 5),
134
      Range<InstructionIndexT>(0, 5)));
135
}
136

137
TEST(MutatorTest, SetupOpTest) {
138
  mt19937 bit_gen;
139
  RandomGenerator rand_gen(&bit_gen);
140
  Mutator mutator(
141
      MutationTypeList(), 0.0,
142
      // allowed_setup_ops
143
      {NO_OP, SCALAR_SUM_OP, MATRIX_VECTOR_PRODUCT_OP, VECTOR_MEAN_OP},
144
      {},  // allowed_predict_ops
145
      {},  // allowed_learn_ops
146
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
147
      &bit_gen, &rand_gen);
148
  EXPECT_TRUE(IsEventually(
149
      function<Op(void)>([&](){
150
        return mutator.SetupOp();
151
      }),
152
      {NO_OP, SCALAR_SUM_OP, MATRIX_VECTOR_PRODUCT_OP, VECTOR_MEAN_OP},
153
      {NO_OP, SCALAR_SUM_OP, MATRIX_VECTOR_PRODUCT_OP, VECTOR_MEAN_OP}));
154
}
155

156
TEST(MutatorTest, PredictOpTest) {
157
  mt19937 bit_gen;
158
  RandomGenerator rand_gen(&bit_gen);
159
  Mutator mutator(
160
      MutationTypeList(), 0.0,
161
      {},  // allowed_setup_ops
162
      // allowed_predict_ops
163
      {NO_OP, SCALAR_SUM_OP, MATRIX_VECTOR_PRODUCT_OP, VECTOR_MEAN_OP},
164
      {},  // allowed_learn_ops
165
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
166
      &bit_gen, &rand_gen);
167
  EXPECT_TRUE(IsEventually(
168
      function<Op(void)>([&](){
169
        return mutator.PredictOp();
170
      }),
171
      {NO_OP, SCALAR_SUM_OP, MATRIX_VECTOR_PRODUCT_OP, VECTOR_MEAN_OP},
172
      {NO_OP, SCALAR_SUM_OP, MATRIX_VECTOR_PRODUCT_OP, VECTOR_MEAN_OP}));
173
}
174

175
TEST(MutatorTest, LearnOpTest) {
176
  mt19937 bit_gen;
177
  RandomGenerator rand_gen(&bit_gen);
178
  Mutator mutator(
179
      MutationTypeList(), 0.0,
180
      {},  // allowed_setup_ops
181
      {},  // allowed_predict_ops
182
      // allowed_learn_ops
183
      {NO_OP, SCALAR_SUM_OP, MATRIX_VECTOR_PRODUCT_OP, VECTOR_MEAN_OP},
184
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
185
      &bit_gen, &rand_gen);
186
  EXPECT_TRUE(IsEventually(
187
      function<Op(void)>([&](){
188
        return mutator.LearnOp();
189
      }),
190
      {NO_OP, SCALAR_SUM_OP, MATRIX_VECTOR_PRODUCT_OP, VECTOR_MEAN_OP},
191
      {NO_OP, SCALAR_SUM_OP, MATRIX_VECTOR_PRODUCT_OP, VECTOR_MEAN_OP}));
192
}
193

194
TEST(MutatorTest, ComponentFunctionTest_SetupPredictLearn) {
195
  mt19937 bit_gen;
196
  RandomGenerator rand_gen(&bit_gen);
197
  Mutator mutator(
198
      MutationTypeList(), 0.0,
199
      {NO_OP, SCALAR_SUM_OP},  // allowed_setup_ops
200
      {NO_OP, SCALAR_SUM_OP},  // allowed_predict_ops
201
      {NO_OP, SCALAR_SUM_OP},  // allowed_learn_ops
202
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
203
      &bit_gen, &rand_gen);
204
  EXPECT_TRUE(IsEventually(
205
      function<ComponentFunctionT(void)>([&](){
206
        return mutator.ComponentFunction();
207
      }),
208
      {kSetupComponentFunction, kPredictComponentFunction,
209
       kLearnComponentFunction},
210
      {kSetupComponentFunction, kPredictComponentFunction,
211
       kLearnComponentFunction}));
212
}
213

214
TEST(MutatorTest, ComponentFunctionTest_Setup) {
215
  mt19937 bit_gen;
216
  RandomGenerator rand_gen(&bit_gen);
217
  Mutator mutator(
218
      MutationTypeList(), 0.0,
219
      {NO_OP, SCALAR_SUM_OP},  // allowed_setup_ops
220
      {},  // allowed_predict_ops
221
      {},  // allowed_learn_ops
222
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
223
      &bit_gen, &rand_gen);
224
  EXPECT_TRUE(IsEventually(
225
      function<ComponentFunctionT(void)>([&](){
226
        return mutator.ComponentFunction();
227
      }),
228
      {kSetupComponentFunction},
229
      {kSetupComponentFunction}));
230
}
231

232
TEST(MutatorTest, ComponentFunctionTest_Predict) {
233
  mt19937 bit_gen;
234
  RandomGenerator rand_gen(&bit_gen);
235
  Mutator mutator(
236
      MutationTypeList(), 0.0,
237
      {},  // allowed_setup_ops
238
      {NO_OP, SCALAR_SUM_OP},  // allowed_predict_ops
239
      {},  // allowed_learn_ops
240
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
241
      &bit_gen, &rand_gen);
242
  EXPECT_TRUE(IsEventually(
243
      function<ComponentFunctionT(void)>([&](){
244
        return mutator.ComponentFunction();
245
      }),
246
      {kPredictComponentFunction},
247
      {kPredictComponentFunction}));
248
}
249

250
TEST(MutatorTest, ComponentFunctionTest_Learn) {
251
  mt19937 bit_gen;
252
  RandomGenerator rand_gen(&bit_gen);
253
  Mutator mutator(
254
      MutationTypeList(), 0.0,
255
      {},  // allowed_setup_ops
256
      {},  // allowed_predict_ops
257
      {NO_OP, SCALAR_SUM_OP},  // allowed_learn_ops
258
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
259
      &bit_gen, &rand_gen);
260
  EXPECT_TRUE(IsEventually(
261
      function<ComponentFunctionT(void)>([&](){
262
        return mutator.ComponentFunction();
263
      }),
264
      {kLearnComponentFunction},
265
      {kLearnComponentFunction}));
266
}
267

268
TEST(MutatorTest, AlterParam) {
269
  RandomGenerator rand_gen;
270
  const Algorithm algorithm = SimpleRandomAlgorithm();
271
  Mutator mutator;
272
  EXPECT_TRUE(IsEventually(
273
      function<IntegerT(void)>([&](){
274
        Algorithm mutated_algorithm = algorithm;
275
        mutator.AlterParam(&mutated_algorithm);
276
        return CountDifferentInstructions(mutated_algorithm, algorithm);
277
      }),
278
      {0, 1}, {1}));
279
  EXPECT_TRUE(IsEventually(
280
      function<IntegerT(void)>([&](){
281
        Algorithm mutated_algorithm = algorithm;
282
        mutator.AlterParam(&mutated_algorithm);
283
        return CountDifferentSetupInstructions(mutated_algorithm, algorithm);
284
      }),
285
      {0, 1}, {1}));
286
  EXPECT_TRUE(IsEventually(
287
      function<IntegerT(void)>([&](){
288
        Algorithm mutated_algorithm = algorithm;
289
        mutator.AlterParam(&mutated_algorithm);
290
        return CountDifferentPredictInstructions(mutated_algorithm, algorithm);
291
      }),
292
      {0, 1}, {1}));
293
  EXPECT_TRUE(IsEventually(
294
      function<IntegerT(void)>([&](){
295
        Algorithm mutated_algorithm = algorithm;
296
        mutator.AlterParam(&mutated_algorithm);
297
        return CountDifferentLearnInstructions(mutated_algorithm, algorithm);
298
      }),
299
      {0, 1}, {1}));
300
}
301

302
TEST(MutatorTest, RandomizeInstruction) {
303
  RandomGenerator rand_gen;
304
  const Algorithm algorithm = SimpleRandomAlgorithm();
305
  Mutator mutator;
306
  EXPECT_TRUE(IsEventually(
307
      function<IntegerT(void)>([&](){
308
        Algorithm mutated_algorithm = algorithm;
309
        mutator.RandomizeInstruction(&mutated_algorithm);
310
        return CountDifferentInstructions(mutated_algorithm, algorithm);
311
      }),
312
      {0, 1}, {1}));
313
  EXPECT_TRUE(IsEventually(
314
      function<IntegerT(void)>([&](){
315
        Algorithm mutated_algorithm = algorithm;
316
        mutator.RandomizeInstruction(&mutated_algorithm);
317
        return CountDifferentSetupInstructions(mutated_algorithm, algorithm);
318
      }),
319
      {0, 1}, {1}));
320
  EXPECT_TRUE(IsEventually(
321
      function<IntegerT(void)>([&](){
322
        Algorithm mutated_algorithm = algorithm;
323
        mutator.RandomizeInstruction(&mutated_algorithm);
324
        return CountDifferentPredictInstructions(mutated_algorithm, algorithm);
325
      }),
326
      {0, 1}, {1}));
327
  EXPECT_TRUE(IsEventually(
328
      function<IntegerT(void)>([&](){
329
        Algorithm mutated_algorithm = algorithm;
330
        mutator.RandomizeInstruction(&mutated_algorithm);
331
        return CountDifferentLearnInstructions(mutated_algorithm, algorithm);
332
      }),
333
      {0, 1}, {1}));
334
}
335

336
TEST(MutatorTest, RandomizeComponentFunction) {
337
  RandomGenerator rand_gen;
338
  const Algorithm algorithm = SimpleRandomAlgorithm();
339
  Mutator mutator;
340
  const IntegerT setup_size = algorithm.setup_.size();
341
  const IntegerT predict_size = algorithm.predict_.size();
342
  const IntegerT learn_size = algorithm.learn_.size();
343
  vector<IntegerT> num_instr = {setup_size, predict_size, learn_size};
344
  const IntegerT max_instructions =
345
      *max_element(num_instr.begin(), num_instr.end());
346
  EXPECT_TRUE(IsEventually(
347
      function<IntegerT(void)>([&](){
348
        Algorithm mutated_algorithm = algorithm;
349
        mutator.RandomizeComponentFunction(&mutated_algorithm);
350
        return CountDifferentInstructions(mutated_algorithm, algorithm);
351
      }),
352
      Range<IntegerT>(0, max_instructions + 1), {max_instructions}));
353
  EXPECT_TRUE(IsEventually(
354
      function<IntegerT(void)>([&](){
355
        Algorithm mutated_algorithm = algorithm;
356
        mutator.RandomizeComponentFunction(&mutated_algorithm);
357
        return CountDifferentSetupInstructions(mutated_algorithm, algorithm);
358
      }),
359
      Range<IntegerT>(0, setup_size + 1),
360
      {setup_size}));
361
  EXPECT_TRUE(IsEventually(
362
      function<IntegerT(void)>([&](){
363
        Algorithm mutated_algorithm = algorithm;
364
        mutator.RandomizeComponentFunction(&mutated_algorithm);
365
        return CountDifferentPredictInstructions(mutated_algorithm, algorithm);
366
      }),
367
      Range<IntegerT>(0, predict_size + 1),
368
      {predict_size}));
369
  EXPECT_TRUE(IsEventually(
370
      function<IntegerT(void)>([&](){
371
        Algorithm mutated_algorithm = algorithm;
372
        mutator.RandomizeComponentFunction(&mutated_algorithm);
373
        return CountDifferentLearnInstructions(mutated_algorithm, algorithm);
374
      }),
375
      Range<IntegerT>(0, learn_size + 1),
376
      {learn_size}));
377
}
378

379
TEST(MutatorTest, IdentityMutationType_WorksCorrectly) {
380
  mt19937 bit_gen;
381
  RandomGenerator rand_gen(&bit_gen);
382
  const Algorithm algorithm = SimpleRandomAlgorithm();
383
  Mutator mutator(
384
      ParseTextFormat<MutationTypeList>(
385
          "mutation_types: [IDENTITY_MUTATION_TYPE] "),
386
      1.0,
387
      {NO_OP, SCALAR_SUM_OP},  // allowed_setup_ops
388
      {NO_OP, SCALAR_SUM_OP},  // allowed_predict_ops
389
      {NO_OP, SCALAR_SUM_OP},  // allowed_learn_ops
390
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
391
      &bit_gen, &rand_gen);
392
  auto mutated_algorithm = make_shared<const Algorithm>(algorithm);
393
  mutator.Mutate(&mutated_algorithm);
394
  EXPECT_EQ(*mutated_algorithm, algorithm);
395
}
396

397
TEST(InsertInstructionMutationTypeTest, CoversComponentFunctions) {
398
  const Algorithm no_op_algorithm = SimpleRandomAlgorithm();
399
  mt19937 bit_gen;
400
  RandomGenerator rand_gen(&bit_gen);
401
  Mutator mutator(
402
      ParseTextFormat<MutationTypeList>(
403
          "mutation_types: [INSERT_INSTRUCTION_MUTATION_TYPE] "),
404
      1.0,  // mutate_prob
405
      {SCALAR_SUM_OP},  // allowed_setup_ops
406
      {SCALAR_SUM_OP},  // allowed_predict_ops
407
      {SCALAR_SUM_OP},  // allowed_learn_ops
408
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
409
      &bit_gen, &rand_gen);
410
  EXPECT_TRUE(IsEventually(
411
    function<IntegerT(void)>([&mutator, no_op_algorithm](){
412
      auto mutated_algorithm = make_shared<const Algorithm>(no_op_algorithm);
413
      mutator.Mutate(&mutated_algorithm);
414
      return DifferentComponentFunction(*mutated_algorithm, no_op_algorithm);
415
    }),
416
    {0, 1, 2}, {0, 1, 2}));
417
}
418

419
TEST(InsertInstructionMutationTypeTest, CoversSetupPositions) {
420
  const Algorithm no_op_algorithm = SimpleNoOpAlgorithm();
421
  const IntegerT component_function_size = no_op_algorithm.setup_.size();
422
  mt19937 bit_gen;
423
  RandomGenerator rand_gen(&bit_gen);
424
  Mutator mutator(
425
      ParseTextFormat<MutationTypeList>(
426
          "mutation_types: [INSERT_INSTRUCTION_MUTATION_TYPE] "),
427
      1.0,  // mutate_prob
428
      {SCALAR_SUM_OP},  // allowed_setup_ops
429
      {},  // allowed_predict_ops
430
      {},  // allowed_learn_ops
431
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
432
      &bit_gen, &rand_gen);
433
  ASSERT_GT(component_function_size, 0);
434
  EXPECT_TRUE(IsEventually(
435
    function<IntegerT(void)>([&mutator, no_op_algorithm](){
436
      auto mutated_algorithm = make_shared<const Algorithm>(no_op_algorithm);
437
      mutator.Mutate(&mutated_algorithm);
438
      return ScalarSumOpPosition(mutated_algorithm->setup_);
439
    }),
440
    Range<IntegerT>(0, component_function_size + 1),
441
    Range<IntegerT>(0, component_function_size + 1),
442
    3));
443
}
444

445
TEST(InsertInstructionMutationTypeTest, CoversPredictPositions) {
446
  const Algorithm no_op_algorithm = SimpleNoOpAlgorithm();
447
  const IntegerT component_function_size = no_op_algorithm.predict_.size();
448
  mt19937 bit_gen;
449
  RandomGenerator rand_gen(&bit_gen);
450
  Mutator mutator(
451
      ParseTextFormat<MutationTypeList>(
452
          "mutation_types: [INSERT_INSTRUCTION_MUTATION_TYPE] "),
453
      1.0,  // mutate_prob
454
      {},  // allowed_setup_ops
455
      {SCALAR_SUM_OP},  // allowed_predict_ops
456
      {},  // allowed_learn_ops
457
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
458
      &bit_gen, &rand_gen);
459
  ASSERT_GT(component_function_size, 0);
460
  EXPECT_TRUE(IsEventually(
461
    function<IntegerT(void)>([&mutator, no_op_algorithm](){
462
      auto mutated_algorithm = make_shared<const Algorithm>(no_op_algorithm);
463
      mutator.Mutate(&mutated_algorithm);
464
      return ScalarSumOpPosition(mutated_algorithm->predict_);
465
    }),
466
    Range<IntegerT>(0, component_function_size + 1),
467
    Range<IntegerT>(0, component_function_size + 1),
468
    3));
469
}
470

471
TEST(InsertInstructionMutationTypeTest, CoversLearnPositions) {
472
  const Algorithm no_op_algorithm = SimpleNoOpAlgorithm();
473
  const IntegerT component_function_size = no_op_algorithm.learn_.size();
474
  mt19937 bit_gen;
475
  RandomGenerator rand_gen(&bit_gen);
476
  Mutator mutator(
477
      ParseTextFormat<MutationTypeList>(
478
          "mutation_types: [INSERT_INSTRUCTION_MUTATION_TYPE] "),
479
      1.0,  // mutate_prob
480
      {},  // allowed_setup_ops
481
      {},  // allowed_predict_ops
482
      {SCALAR_SUM_OP},  // allowed_learn_ops
483
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
484
      &bit_gen, &rand_gen);
485
  ASSERT_GT(component_function_size, 0);
486
  EXPECT_TRUE(IsEventually(
487
    function<IntegerT(void)>([&mutator, no_op_algorithm](){
488
      auto mutated_algorithm = make_shared<const Algorithm>(no_op_algorithm);
489
      mutator.Mutate(&mutated_algorithm);
490
      return ScalarSumOpPosition(mutated_algorithm->learn_);
491
    }),
492
    Range<IntegerT>(0, component_function_size + 1),
493
    Range<IntegerT>(0, component_function_size + 1),
494
    3));
495
}
496

497
TEST(InsertInstructionMutationTypeTest, InsertsWhenUnderMinSize) {
498
  const Algorithm no_op_algorithm = SimpleNoOpAlgorithm();
499
  const IntegerT setup_component_function_size = no_op_algorithm.setup_.size();
500
  const IntegerT predict_component_function_size =
501
      no_op_algorithm.predict_.size();
502
  const IntegerT learn_component_function_size = no_op_algorithm.learn_.size();
503
  mt19937 bit_gen;
504
  RandomGenerator rand_gen(&bit_gen);
505
  Mutator mutator(
506
      ParseTextFormat<MutationTypeList>(
507
          "mutation_types: [INSERT_INSTRUCTION_MUTATION_TYPE] "),
508
      1.0,  // mutate_prob
509
      {SCALAR_SUM_OP},  // allowed_setup_ops
510
      {SCALAR_SUM_OP},  // allowed_predict_ops
511
      {SCALAR_SUM_OP},  // allowed_learn_ops
512
      100, 10000, 100, 10000, 100, 10000,  // min/max component function sizes
513
      &bit_gen, &rand_gen);
514
  auto mutated_algorithm = make_shared<const Algorithm>(no_op_algorithm);
515
  mutator.Mutate(&mutated_algorithm);
516
  EXPECT_TRUE(mutated_algorithm->setup_.size() ==
517
                  setup_component_function_size + 1 ||
518
              mutated_algorithm->predict_.size() ==
519
                  predict_component_function_size + 1 ||
520
              mutated_algorithm->learn_.size() ==
521
                  learn_component_function_size + 1);
522
}
523

524
TEST(InsertInstructionMutationTypeTest, DoesNotInsertWhenOverMaxSize) {
525
  const Algorithm no_op_algorithm = SimpleNoOpAlgorithm();
526
  mt19937 bit_gen;
527
  RandomGenerator rand_gen(&bit_gen);
528
  Mutator mutator(
529
      ParseTextFormat<MutationTypeList>(
530
          "mutation_types: [INSERT_INSTRUCTION_MUTATION_TYPE] "),
531
      1.0,  // mutate_prob
532
      {SCALAR_SUM_OP},  // allowed_setup_ops
533
      {SCALAR_SUM_OP},  // allowed_predict_ops
534
      {SCALAR_SUM_OP},  // allowed_learn_ops
535
      0, 1, 0, 1, 0, 1,  // min/max component function sizes
536
      &bit_gen, &rand_gen);
537
  auto mutated_algorithm = make_shared<const Algorithm>(no_op_algorithm);
538
  mutator.Mutate(&mutated_algorithm);
539
  EXPECT_EQ(*mutated_algorithm, no_op_algorithm);
540
}
541

542
TEST(InsertInstructionMutationTypeTest, CoversSetupInstructions) {
543
  const Algorithm empty_algorithm;
544
  mt19937 bit_gen;
545
  RandomGenerator rand_gen(&bit_gen);
546
  Mutator mutator(
547
      ParseTextFormat<MutationTypeList>(
548
          "mutation_types: [INSERT_INSTRUCTION_MUTATION_TYPE] "),
549
      1.0,  // mutate_prob
550
      {SCALAR_SUM_OP, SCALAR_DIFF_OP},  // allowed_setup_ops
551
      {},  // allowed_predict_ops
552
      {},  // allowed_learn_ops
553
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
554
      &bit_gen, &rand_gen);
555
  EXPECT_TRUE(IsEventually(
556
    function<IntegerT(void)>([&mutator, empty_algorithm](){
557
      auto mutated_algorithm = make_shared<const Algorithm>(empty_algorithm);
558
      mutator.Mutate(&mutated_algorithm);
559
      if (mutated_algorithm->setup_.size() == 1) {
560
        return static_cast<IntegerT>(mutated_algorithm->setup_[0]->op_);
561
      } else {
562
        return static_cast<IntegerT>(-1);
563
      }
564
    }),
565
    {SCALAR_SUM_OP, SCALAR_DIFF_OP}, {SCALAR_SUM_OP, SCALAR_DIFF_OP}, 3));
566
}
567

568
TEST(InsertInstructionMutationTypeTest, CoversPredictInstructions) {
569
  const Algorithm empty_algorithm;
570
  mt19937 bit_gen;
571
  RandomGenerator rand_gen(&bit_gen);
572
  Mutator mutator(
573
      ParseTextFormat<MutationTypeList>(
574
          "mutation_types: [INSERT_INSTRUCTION_MUTATION_TYPE] "),
575
      1.0,  // mutate_prob
576
      {},  // allowed_setup_ops
577
      {SCALAR_SUM_OP, SCALAR_DIFF_OP},  // allowed_predict_ops
578
      {},  // allowed_learn_ops
579
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
580
      &bit_gen, &rand_gen);
581
  EXPECT_TRUE(IsEventually(
582
    function<IntegerT(void)>([&mutator, empty_algorithm](){
583
      auto mutated_algorithm = make_shared<const Algorithm>(empty_algorithm);
584
      mutator.Mutate(&mutated_algorithm);
585
      if (mutated_algorithm->predict_.size() == 1) {
586
        return static_cast<IntegerT>(mutated_algorithm->predict_[0]->op_);
587
      } else {
588
        return static_cast<IntegerT>(-1);
589
      }
590
    }),
591
    {SCALAR_SUM_OP, SCALAR_DIFF_OP}, {SCALAR_SUM_OP, SCALAR_DIFF_OP}, 3));
592
}
593

594
TEST(InsertInstructionMutationTypeTest, CoversLearnInstructions) {
595
  const Algorithm empty_algorithm;
596
  mt19937 bit_gen;
597
  RandomGenerator rand_gen(&bit_gen);
598
  Mutator mutator(
599
      ParseTextFormat<MutationTypeList>(
600
          "mutation_types: [INSERT_INSTRUCTION_MUTATION_TYPE] "),
601
      1.0,  // mutate_prob
602
      {},  // allowed_setup_ops
603
      {},  // allowed_predict_ops
604
      {SCALAR_SUM_OP, SCALAR_DIFF_OP},  // allowed_learn_ops
605
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
606
      &bit_gen, &rand_gen);
607
  EXPECT_TRUE(IsEventually(
608
    function<IntegerT(void)>([&mutator, empty_algorithm](){
609
      auto mutated_algorithm = make_shared<const Algorithm>(empty_algorithm);
610
      mutator.Mutate(&mutated_algorithm);
611
      if (mutated_algorithm->learn_.size() == 1) {
612
        return static_cast<IntegerT>(mutated_algorithm->learn_[0]->op_);
613
      } else {
614
        return static_cast<IntegerT>(-1);
615
      }
616
    }),
617
    {SCALAR_SUM_OP, SCALAR_DIFF_OP}, {SCALAR_SUM_OP, SCALAR_DIFF_OP}, 3));
618
}
619

620
TEST(RemoveInstructionMutationTypeTest, CoversComponentFunctions) {
621
  const Algorithm random_algorithm = SimpleRandomAlgorithm();
622
  mt19937 bit_gen;
623
  RandomGenerator rand_gen(&bit_gen);
624
  Mutator mutator(
625
      ParseTextFormat<MutationTypeList>(
626
          "mutation_types: [REMOVE_INSTRUCTION_MUTATION_TYPE] "),
627
      1.0, {NO_OP}, {NO_OP}, {NO_OP},
628
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
629
      &bit_gen, &rand_gen);
630
  EXPECT_TRUE(IsEventually(
631
    function<IntegerT(void)>([&mutator, random_algorithm](){
632
      auto mutated_algorithm = make_shared<const Algorithm>(random_algorithm);
633
      mutator.Mutate(&mutated_algorithm);
634
      return DifferentComponentFunction(*mutated_algorithm, random_algorithm);
635
    }),
636
    {0, 1, 2}, {0, 1, 2}, 3));
637
}
638

639
TEST(RemoveInstructionMutationTypeTest, CoversSetupPositions) {
640
  const Algorithm algorithm = SimpleIncreasingDataAlgorithm();
641
  const IntegerT component_function_size = algorithm.setup_.size();
642
  mt19937 bit_gen;
643
  RandomGenerator rand_gen(&bit_gen);
644
  Mutator mutator(
645
      ParseTextFormat<MutationTypeList>(
646
          "mutation_types: [REMOVE_INSTRUCTION_MUTATION_TYPE] "),
647
      1.0,  // mutate_prob
648
      {NO_OP},  // allowed_setup_ops
649
      {},  // allowed_predict_ops
650
      {},  // allowed_learn_ops
651
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
652
      &bit_gen, &rand_gen);
653
  ASSERT_GT(component_function_size, 0);
654
  EXPECT_TRUE(IsEventually(
655
    function<IntegerT(void)>([&mutator, algorithm](){
656
      auto mutated_algorithm = make_shared<const Algorithm>(algorithm);
657
      mutator.Mutate(&mutated_algorithm);
658
      return MissingDataInComponentFunction(
659
          algorithm.setup_, mutated_algorithm->setup_);
660
    }),
661
    Range<IntegerT>(0, component_function_size),
662
    Range<IntegerT>(0, component_function_size),
663
    3));
664
}
665

666
TEST(RemoveInstructionMutationTypeTest, CoversPredictPositions) {
667
  const Algorithm algorithm = SimpleIncreasingDataAlgorithm();
668
  const IntegerT component_function_size = algorithm.predict_.size();
669
  mt19937 bit_gen;
670
  RandomGenerator rand_gen(&bit_gen);
671
  Mutator mutator(
672
      ParseTextFormat<MutationTypeList>(
673
          "mutation_types: [REMOVE_INSTRUCTION_MUTATION_TYPE] "),
674
      1.0,  // mutate_prob
675
      {},  // allowed_setup_ops
676
      {NO_OP},  // allowed_predict_ops
677
      {},  // allowed_learn_ops
678
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
679
      &bit_gen, &rand_gen);
680
  ASSERT_GT(component_function_size, 0);
681
  EXPECT_TRUE(IsEventually(
682
    function<IntegerT(void)>([&mutator, algorithm](){
683
      auto mutated_algorithm = make_shared<const Algorithm>(algorithm);
684
      mutator.Mutate(&mutated_algorithm);
685
      return MissingDataInComponentFunction(
686
          algorithm.predict_, mutated_algorithm->predict_);
687
    }),
688
    Range<IntegerT>(0, component_function_size),
689
    Range<IntegerT>(0, component_function_size),
690
    3));
691
}
692

693
TEST(RemoveInstructionMutationTypeTest, CoversLearnPositions) {
694
  const Algorithm algorithm = SimpleIncreasingDataAlgorithm();
695
  const IntegerT component_function_size = algorithm.learn_.size();
696
  mt19937 bit_gen;
697
  RandomGenerator rand_gen(&bit_gen);
698
  Mutator mutator(
699
      ParseTextFormat<MutationTypeList>(
700
          "mutation_types: [REMOVE_INSTRUCTION_MUTATION_TYPE] "),
701
      1.0,  // mutate_prob
702
      {},  // allowed_setup_ops
703
      {},  // allowed_predict_ops
704
      {NO_OP},  // allowed_learn_ops
705
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
706
      &bit_gen, &rand_gen);
707
  ASSERT_GT(component_function_size, 0);
708
  EXPECT_TRUE(IsEventually(
709
    function<IntegerT(void)>([&mutator, algorithm](){
710
      auto mutated_algorithm = make_shared<const Algorithm>(algorithm);
711
      mutator.Mutate(&mutated_algorithm);
712
      return MissingDataInComponentFunction(
713
          algorithm.learn_, mutated_algorithm->learn_);
714
    }),
715
    Range<IntegerT>(0, component_function_size),
716
    Range<IntegerT>(0, component_function_size),
717
    3));
718
}
719

720
TEST(RemoveInstructionMutationTypeTest, DoesNotRemoveWhenUnderMinSize) {
721
  const Algorithm no_op_algorithm = SimpleNoOpAlgorithm();
722
  mt19937 bit_gen;
723
  RandomGenerator rand_gen(&bit_gen);
724
  Mutator mutator(
725
      ParseTextFormat<MutationTypeList>(
726
          "mutation_types: [REMOVE_INSTRUCTION_MUTATION_TYPE] "),
727
      1.0,  // mutate_prob
728
      {SCALAR_SUM_OP},  // allowed_setup_ops
729
      {SCALAR_SUM_OP},  // allowed_predict_ops
730
      {SCALAR_SUM_OP},  // allowed_learn_ops
731
      100, 10000, 100, 10000, 100, 10000,  // min/max component function sizes
732
      &bit_gen, &rand_gen);
733
  auto mutated_algorithm = make_shared<const Algorithm>(no_op_algorithm);
734
  mutator.Mutate(&mutated_algorithm);
735
  EXPECT_EQ(*mutated_algorithm, no_op_algorithm);
736
}
737

738
TEST(RemoveInstructionMutationTypeTest, RemovesWhenOverMaxSize) {
739
  const Algorithm no_op_algorithm = SimpleNoOpAlgorithm();
740
  const IntegerT setup_component_function_size = no_op_algorithm.setup_.size();
741
  const IntegerT predict_component_function_size =
742
      no_op_algorithm.predict_.size();
743
  const IntegerT learn_component_function_size = no_op_algorithm.learn_.size();
744
  mt19937 bit_gen;
745
  RandomGenerator rand_gen(&bit_gen);
746
  Mutator mutator(
747
      ParseTextFormat<MutationTypeList>(
748
          "mutation_types: [REMOVE_INSTRUCTION_MUTATION_TYPE] "),
749
      1.0,  // mutate_prob
750
      {SCALAR_SUM_OP},  // allowed_setup_ops
751
      {SCALAR_SUM_OP},  // allowed_predict_ops
752
      {SCALAR_SUM_OP},  // allowed_learn_ops
753
      0, 1, 0, 1, 0, 1,  // min/max component function sizes
754
      &bit_gen, &rand_gen);
755
  auto mutated_algorithm = make_shared<const Algorithm>(no_op_algorithm);
756
  mutator.Mutate(&mutated_algorithm);
757
  EXPECT_TRUE(mutated_algorithm->setup_.size() ==
758
                  setup_component_function_size - 1 ||
759
              mutated_algorithm->predict_.size() ==
760
                  predict_component_function_size - 1 ||
761
              mutated_algorithm->learn_.size() ==
762
                  learn_component_function_size - 1);
763
}
764

765
TEST(TradeInstructionMutationTypeTest, CoversComponentFunctions) {
766
  const Algorithm random_algorithm = SimpleRandomAlgorithm();
767
  mt19937 bit_gen;
768
  RandomGenerator rand_gen(&bit_gen);
769
  Mutator mutator(
770
      ParseTextFormat<MutationTypeList>(
771
          "mutation_types: [TRADE_INSTRUCTION_MUTATION_TYPE] "),
772
      1.0, {NO_OP}, {NO_OP}, {NO_OP},
773
      0, 10000, 0, 10000, 0, 10000,  // min/max component function sizes
774
      &bit_gen, &rand_gen);
775
  EXPECT_TRUE(IsEventually(
776
    function<IntegerT(void)>([&mutator, random_algorithm](){
777
      auto mutated_algorithm = make_shared<const Algorithm>(random_algorithm);
778
      mutator.Mutate(&mutated_algorithm);
779
      return DifferentComponentFunction(*mutated_algorithm, random_algorithm);
780
    }),
781
    {-1, 0, 1, 2}, {0, 1, 2}, 3));
782
}
783

784
TEST(TradeInstructionMutationTypeTest, PreservesSizes) {
785
  const Algorithm random_algorithm = SimpleRandomAlgorithm();
786
  mt19937 bit_gen;
787
  RandomGenerator rand_gen(&bit_gen);
788
  Mutator mutator(
789
      ParseTextFormat<MutationTypeList>(
790
          "mutation_types: [TRADE_INSTRUCTION_MUTATION_TYPE] "),
791
      1.0, {NO_OP}, {NO_OP}, {NO_OP},
792
      0, 10000, 0, 10000, 0, 10000,  // min/max prog. sizes
793
      &bit_gen, &rand_gen);
794
  auto mutated_algorithm = make_shared<const Algorithm>(random_algorithm);
795
  mutator.Mutate(&mutated_algorithm);
796
  EXPECT_EQ(mutated_algorithm->setup_.size(), random_algorithm.setup_.size());
797
  EXPECT_EQ(mutated_algorithm->predict_.size(),
798
            random_algorithm.predict_.size());
799
  EXPECT_EQ(mutated_algorithm->learn_.size(), random_algorithm.learn_.size());
800
}
801

802
TEST(MutatorTest, RandomizeAlgorithm) {
803
  RandomGenerator rand_gen;
804
  mt19937 bit_gen;
805
  const Algorithm algorithm = SimpleRandomAlgorithm();
806
  const IntegerT setup_size = algorithm.setup_.size();
807
  const IntegerT predict_size = algorithm.predict_.size();
808
  const IntegerT learn_size = algorithm.learn_.size();
809
  Mutator mutator(
810
      ParseTextFormat<MutationTypeList>(
811
          "mutation_types: [RANDOMIZE_ALGORITHM_MUTATION_TYPE] "),
812
      1.0,
813
      {NO_OP, SCALAR_SUM_OP, MATRIX_VECTOR_PRODUCT_OP, VECTOR_MEAN_OP},
814
      {NO_OP, SCALAR_SUM_OP, MATRIX_VECTOR_PRODUCT_OP, VECTOR_MEAN_OP},
815
      {NO_OP, SCALAR_SUM_OP, MATRIX_VECTOR_PRODUCT_OP, VECTOR_MEAN_OP},
816
      setup_size, setup_size + 1,
817
      predict_size, predict_size + 1,
818
      learn_size, learn_size + 1,
819
      &bit_gen, &rand_gen);
820
  const IntegerT num_instr = setup_size + predict_size + learn_size;
821
  EXPECT_TRUE(IsEventually(
822
      function<IntegerT(void)>([&](){
823
        Algorithm mutated_algorithm = algorithm;
824
        mutator.RandomizeAlgorithm(&mutated_algorithm);
825
        return CountDifferentInstructions(mutated_algorithm, algorithm);
826
      }),
827
      Range<IntegerT>(0, num_instr + 1), {num_instr}));
828
}
829

830
}  // namespace automl_zero
831