henad_core/explore/search/
mod.rs

1//! Searches that pick the configs to run from the results of the configs run before.
2//!
3//! A search varies the factors of its space. A candidate is one point of that space, held as a [`Genome`] and decoded
4//! into a config. Evaluating a candidate runs its config for a fixed number of replicates and reports the watched
5//! output columns of each run. A searcher proposes candidates a batch at a time, and is told their evaluations
6//! before its next ask. A re-evaluation runs more replicates of a candidate already evaluated, and its values count
7//! toward that candidate. The budget counts evaluations, re-evaluations included.
8
9pub mod evaluation_log;
10pub mod genetic;
11pub mod genome;
12pub mod hill_climb;
13pub mod pse;
14pub mod random;
15
16#[cfg(test)]
17mod tests;
18
19use std::cmp::Ordering;
20use std::collections::{BTreeMap, BTreeSet};
21use std::fmt;
22use std::str::FromStr;
23
24use crate::explore::design::MAX_CONFIGS;
25use crate::explore::factor::FactorSpec;
26use crate::explore::search::evaluation_log::CandidateRecord;
27use crate::explore::search::genetic::{GeneticAlgorithm, GeneticSettings};
28use crate::explore::search::genome::{ConfigKey, Genome, SearchSpace};
29use crate::explore::search::hill_climb::{HillClimb, HillClimbSettings};
30use crate::explore::search::pse::{ArchiveEntry, PatternCell, PatternSpaceExploration, PatternSpaceSettings};
31use crate::explore::search::random::RandomSearch;
32use crate::explore::seed::search_seed;
33
34/// A search method, driven by asking it for candidates and telling it their evaluations.
35///
36/// Every [`Searcher::ask`] is followed by one [`Searcher::tell`] with the evaluations of the candidates it returned.
37/// A searcher draws only from its seed, so one sequence of asks and tells always produces the same candidates.
38pub trait Searcher {
39    /// Returns up to `max` candidates to evaluate next.
40    ///
41    /// Note that an ask can return fewer than `max` candidates, as at the end of a generation, of the initial samples
42    /// or of the budget, and returns no candidates once the budget is spent.
43    fn ask(&mut self, max: usize) -> Vec<Candidate>;
44
45    /// Accepts the evaluations of the candidates that the last ask returned, sorted by candidate id.
46    ///
47    /// An evaluation of a candidate that the searcher is not waiting for is ignored.
48    fn tell(&mut self, evaluations: &[Evaluation]);
49
50    /// Returns whether the search has issued its whole budget and been told every evaluation.
51    fn is_done(&self) -> bool;
52
53    /// Returns every candidate scored so far, best first, with the finished generations and the archive.
54    ///
55    /// Note that the report copies every candidate. [`Self::best`], [`Self::ranking_entry`] and
56    /// [`Self::archive_entry`] read one candidate or cell at a time.
57    fn report(&self) -> SearchReport;
58
59    /// Returns the best candidate so far, or `None` before any evaluation or for a Pattern Space Exploration.
60    fn best(&self) -> Option<RankingEntry> {
61        None
62    }
63
64    /// Returns candidate `candidate_id` with its objective over every replicate it has, or `None` for a candidate
65    /// never told or a Pattern Space Exploration.
66    fn ranking_entry(&self, _candidate_id: u64) -> Option<RankingEntry> {
67        None
68    }
69
70    /// Returns the archive entry of `cell`, or `None` for an empty cell or a search other than a Pattern Space
71    /// Exploration.
72    fn archive_entry(&self, _cell: PatternCell) -> Option<ArchiveEntry> {
73        None
74    }
75
76    /// Number of filled cells in the archive of a Pattern Space Exploration, 0 for any other search.
77    fn filled_cells(&self) -> u64 {
78        0
79    }
80
81    /// Finished generations of a genetic algorithm, in order, empty for any other search.
82    fn generations(&self) -> &[GenerationSummary] {
83        &[]
84    }
85
86    /// Returns the settings that a Pattern Space Exploration uses to place outputs, each axis with its range, or
87    /// `None` while an automatic range waits for the initial samples or for any other search.
88    fn pattern_settings(&self) -> Option<&PatternSpaceSettings> {
89        None
90    }
91}
92
93/// A point of a search space to evaluate.
94#[derive(Debug, Clone, PartialEq)]
95pub struct Candidate {
96    /// Position of the candidate among every candidate of the search, counting from 0.
97    pub id: u64,
98    /// Point of the space the candidate decodes from.
99    pub genome: Genome,
100    /// Replicate index of the candidate's first run.
101    ///
102    /// A first evaluation starts at 0. A re-evaluation starts past every replicate its candidate has.
103    pub replicate_offset: u64,
104    /// Source of the candidate's genome.
105    pub origin: CandidateOrigin,
106}
107
108/// Source of a candidate's genome.
109#[derive(Debug, Clone, Copy, PartialEq, Eq)]
110pub enum CandidateOrigin {
111    /// Drawn uniformly from the space.
112    Random,
113    /// Drawn uniformly from the space when a hill climb starts over.
114    Restart,
115    /// A step away from hill climb incumbent `parent_id`.
116    Neighbor {
117        /// Id of the incumbent the step starts from.
118        parent_id: u64,
119    },
120    /// Candidate `parent_id` with some genes changed.
121    Mutation {
122        /// Id of the candidate the genes come from.
123        parent_id: u64,
124    },
125    /// Genes taken from two parents, then mutated.
126    Crossover {
127        /// Id of the parent that won the first tournament.
128        first_parent_id: u64,
129        /// Id of the parent that won the second tournament.
130        second_parent_id: u64,
131    },
132    /// More replicates of candidate `candidate_id`.
133    Reevaluation {
134        /// Id of the candidate evaluated again.
135        candidate_id: u64,
136    },
137}
138
139impl CandidateOrigin {
140    /// Returns the origin's name in `evaluations.csv`, as in `crossover`.
141    pub fn as_str(self) -> &'static str {
142        match self {
143            Self::Random => "random",
144            Self::Restart => "restart",
145            Self::Neighbor { .. } => "neighbor",
146            Self::Mutation { .. } => "mutation",
147            Self::Crossover { .. } => "crossover",
148            Self::Reevaluation { .. } => "reevaluation",
149        }
150    }
151
152    /// Returns the ids of the parents the genome was bred from, the first parent first.
153    ///
154    /// A re-evaluation has no parents. [`Self::reevaluated_id`] returns the id of the candidate it repeats.
155    pub fn parent_ids(self) -> [Option<u64>; 2] {
156        match self {
157            Self::Random | Self::Restart | Self::Reevaluation { .. } => [None, None],
158            Self::Neighbor { parent_id } | Self::Mutation { parent_id } => [Some(parent_id), None],
159            Self::Crossover {
160                first_parent_id,
161                second_parent_id,
162            } => [Some(first_parent_id), Some(second_parent_id)],
163        }
164    }
165
166    /// Returns the candidate a re-evaluation adds replicates to, or `None` for any other origin.
167    pub fn reevaluated_id(self) -> Option<u64> {
168        match self {
169            Self::Reevaluation { candidate_id } => Some(candidate_id),
170            _ => None,
171        }
172    }
173}
174
175/// Values the runs of a candidate reported.
176#[derive(Debug, Clone, PartialEq)]
177pub struct Evaluation {
178    /// Id of the candidate evaluated.
179    pub candidate_id: u64,
180    /// Values of the watched columns, one row per replicate in replicate order.
181    ///
182    /// A row holds the columns that [`SearchSpec::watched_columns`] lists, in that order. `None` marks a failed run or
183    /// a value the run never reached.
184    pub outputs: Vec<Vec<Option<f64>>>,
185}
186
187/// Output a search scores candidates by, and the direction it prefers.
188#[derive(Debug, Clone, PartialEq, Eq)]
189pub struct Objective {
190    /// Output column, a reducer column such as `Infected:max`.
191    pub column: String,
192    /// Direction the search prefers.
193    pub goal: Goal,
194    /// Rule that folds the replicates of a candidate into one value.
195    pub aggregate: Aggregate,
196}
197
198impl Objective {
199    /// Returns the objective over the replicates of `evaluation`, from the first watched column.
200    ///
201    /// A failed replicate, missing or not finite, counts as [`Goal::worst`].
202    pub fn score(&self, evaluation: &Evaluation) -> f64 {
203        self.score_values(evaluation.outputs.iter().map(|row| row.first().copied().flatten()))
204    }
205
206    /// Returns the objective over replicate values `values`, with [`Goal::worst`] as the value of a failed replicate.
207    fn score_values(&self, values: impl Iterator<Item = Option<f64>>) -> f64 {
208        let worst = self.goal.worst();
209        let mut values: Vec<f64> = values
210            .map(|value| value.filter(|value| value.is_finite()).unwrap_or(worst))
211            .collect();
212        self.aggregate.combine(&mut values).unwrap_or(worst)
213    }
214}
215
216/// Direction of an objective.
217#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
218pub enum Goal {
219    /// Lower values are better.
220    #[default]
221    Minimize,
222    /// Higher values are better.
223    Maximize,
224}
225
226impl Goal {
227    /// Returns the goal's name, as in `minimize`.
228    pub fn as_str(self) -> &'static str {
229        match self {
230            Self::Minimize => "minimize",
231            Self::Maximize => "maximize",
232        }
233    }
234
235    /// Value a failed replicate counts as, infinitely far from the goal.
236    pub fn worst(self) -> f64 {
237        match self {
238            Self::Minimize => f64::INFINITY,
239            Self::Maximize => f64::NEG_INFINITY,
240        }
241    }
242
243    /// Returns whether `value` is strictly better than `reference`.
244    pub fn is_better(self, value: f64, reference: f64) -> bool {
245        self.compare(value, reference) == Ordering::Less
246    }
247
248    /// Orders two values, the better one first.
249    ///
250    /// Note that `NaN` ties with every value.
251    pub fn compare(self, first: f64, second: f64) -> Ordering {
252        let ordering = first.partial_cmp(&second).unwrap_or(Ordering::Equal);
253        match self {
254            Self::Minimize => ordering,
255            Self::Maximize => ordering.reverse(),
256        }
257    }
258}
259
260impl FromStr for Goal {
261    type Err = SearchKeywordError;
262
263    /// Reads a goal as [`Goal::as_str`] writes it.
264    fn from_str(raw: &str) -> Result<Self, Self::Err> {
265        match raw {
266            "minimize" => Ok(Self::Minimize),
267            "maximize" => Ok(Self::Maximize),
268            _ => Err(SearchKeywordError {
269                raw: raw.to_owned(),
270                expected: &["minimize", "maximize"],
271            }),
272        }
273    }
274}
275
276/// Rule that folds the replicate values of a candidate into one value.
277#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
278pub enum Aggregate {
279    /// Mean of the values.
280    Mean,
281    /// Middle value, or the mean of the middle two for an even count.
282    #[default]
283    Median,
284}
285
286impl Aggregate {
287    /// Returns the aggregate's name, as in `median`.
288    pub fn as_str(self) -> &'static str {
289        match self {
290            Self::Mean => "mean",
291            Self::Median => "median",
292        }
293    }
294
295    /// Returns the mean or median of `values`, or `None` when `values` is empty.
296    ///
297    /// The median sorts `values` in place.
298    pub fn combine(self, values: &mut [f64]) -> Option<f64> {
299        if values.is_empty() {
300            return None;
301        }
302        match self {
303            Self::Mean => Some(values.iter().sum::<f64>() / values.len() as f64),
304            Self::Median => {
305                values.sort_unstable_by(f64::total_cmp);
306                let middle = values.len() / 2;
307                if values.len() % 2 == 1 {
308                    Some(values[middle])
309                } else {
310                    Some(f64::midpoint(values[middle - 1], values[middle]))
311                }
312            }
313        }
314    }
315}
316
317impl FromStr for Aggregate {
318    type Err = SearchKeywordError;
319
320    /// Reads an aggregate as [`Aggregate::as_str`] writes it.
321    fn from_str(raw: &str) -> Result<Self, Self::Err> {
322        match raw {
323            "mean" => Ok(Self::Mean),
324            "median" => Ok(Self::Median),
325            _ => Err(SearchKeywordError {
326                raw: raw.to_owned(),
327                expected: &["mean", "median"],
328            }),
329        }
330    }
331}
332
333/// Text that matches no goal or aggregate.
334#[derive(Debug, Clone, PartialEq, Eq)]
335pub struct SearchKeywordError {
336    /// Text as given.
337    pub raw: String,
338    /// Names that the keyword accepts.
339    pub expected: &'static [&'static str],
340}
341
342impl fmt::Display for SearchKeywordError {
343    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
344        write!(
345            f,
346            "unknown value '{}', expected {}",
347            self.raw,
348            self.expected.join(" or ")
349        )
350    }
351}
352
353impl std::error::Error for SearchKeywordError {}
354
355/// State of a search, for its output tables and views.
356#[derive(Debug, Clone, Default, PartialEq)]
357pub struct SearchReport {
358    /// Every candidate a random search, hill climb or genetic algorithm has scored, best first.
359    ///
360    /// Re-evaluations appear under the candidate they repeat. Among equal objectives the lower id comes first.
361    pub ranking: Vec<RankingEntry>,
362    /// Every finished generation of a genetic algorithm, in order.
363    pub generations: Vec<GenerationSummary>,
364    /// Every filled cell of a Pattern Space Exploration archive, in cell order.
365    pub archive: Vec<ArchiveEntry>,
366}
367
368impl SearchReport {
369    /// Returns the best candidate so far, or `None` before any evaluation or for a Pattern Space Exploration.
370    pub fn best(&self) -> Option<&RankingEntry> {
371        self.ranking.first()
372    }
373
374    /// Returns candidate `candidate_id` from the ranking, or `None` for a candidate missing from the ranking.
375    pub fn ranking_entry(&self, candidate_id: u64) -> Option<&RankingEntry> {
376        self.ranking.iter().find(|entry| entry.candidate_id == candidate_id)
377    }
378
379    /// Returns the archive entry of `cell`, or `None` for a cell missing from the archive.
380    pub fn archive_entry(&self, cell: PatternCell) -> Option<&ArchiveEntry> {
381        self.archive
382            .binary_search_by(|entry| entry.cell.cmp(&cell))
383            .ok()
384            .map(|index| &self.archive[index])
385    }
386}
387
388/// A candidate of a ranking, with its objective over every replicate it has.
389#[derive(Debug, Clone, PartialEq)]
390pub struct RankingEntry {
391    /// Id of the candidate.
392    pub candidate_id: u64,
393    /// Objective over every replicate, with [`Goal::worst`] as the value of a failed replicate.
394    pub objective: f64,
395    /// Number of replicates behind the objective, re-evaluations included.
396    pub replicate_count: u64,
397    /// Number of replicates whose value was missing or not finite.
398    pub failed_count: u64,
399    /// Number of evaluations of the candidate, the first one and each re-evaluation.
400    pub evaluations: u64,
401    /// Index of the ask that first returned the candidate, counting from 0.
402    pub first_batch: u64,
403}
404
405/// Objectives of the members of one generation of a genetic algorithm.
406#[derive(Debug, Clone, PartialEq)]
407pub struct GenerationSummary {
408    /// Index of the generation, counting from 0.
409    pub generation: u64,
410    /// Best fitness among the members.
411    pub best: f64,
412    /// Median fitness of the members.
413    pub median: f64,
414    /// Worst fitness among the members.
415    pub worst: f64,
416}
417
418/// A search as written, with its space still in the form that a spec uses.
419#[derive(Debug, Clone, PartialEq)]
420pub struct SearchSpec {
421    /// Search method, with its settings.
422    pub algorithm: SearchAlgorithm,
423    /// Maximum number of evaluations, re-evaluations included.
424    pub max_evaluations: u64,
425    /// Maximum number of candidates that one ask returns.
426    pub batch_size: usize,
427    /// Output a random search, hill climb or genetic algorithm scores. A Pattern Space Exploration has no objective.
428    pub objective: Option<Objective>,
429    /// Factors the search varies. A range with no step spans every value from its `min` to its `max`.
430    pub space: Vec<FactorSpec>,
431}
432
433impl SearchSpec {
434    /// Checks the budget, the batch size, the objective and the settings of the algorithm.
435    ///
436    /// A batch holds at most [`MAX_CONFIGS`] candidates, the same limit as the configs of a sweep's plan.
437    ///
438    /// # Errors
439    ///
440    /// Returns [`SearchSpecError`] for no evaluations, a batch size of 0 or past [`MAX_CONFIGS`], a missing objective
441    /// for a random search, hill climb or genetic algorithm, an objective given to a Pattern Space Exploration, or a
442    /// setting outside its range.
443    pub fn check(&self) -> Result<(), SearchSpecError> {
444        if self.max_evaluations == 0 {
445            return Err(SearchSpecError::NoEvaluations);
446        }
447        if self.batch_size == 0 {
448            return Err(SearchSpecError::NoBatch);
449        }
450        if self.batch_size > MAX_CONFIGS {
451            return Err(SearchSpecError::BatchTooLarge {
452                batch_size: self.batch_size,
453            });
454        }
455        match (&self.algorithm, &self.objective) {
456            (SearchAlgorithm::PatternSpaceExploration(settings), None) => settings.check(),
457            (SearchAlgorithm::PatternSpaceExploration(_), Some(_)) => Err(SearchSpecError::UnusedObjective),
458            (algorithm, None) => Err(SearchSpecError::MissingObjective {
459                algorithm: algorithm.as_str(),
460            }),
461            (SearchAlgorithm::Random, Some(_)) => Ok(()),
462            (SearchAlgorithm::HillClimb(settings), Some(_)) => settings.check(),
463            (SearchAlgorithm::Genetic(settings), Some(_)) => settings.check(),
464        }
465    }
466
467    /// Returns the output columns each replicate of an evaluation reports, in the order [`Evaluation::outputs`]
468    /// holds them.
469    pub fn watched_columns(&self) -> Vec<&str> {
470        match &self.algorithm {
471            SearchAlgorithm::PatternSpaceExploration(settings) => {
472                vec![settings.x_axis.column.as_str(), settings.y_axis.column.as_str()]
473            }
474            SearchAlgorithm::Random | SearchAlgorithm::HillClimb(_) | SearchAlgorithm::Genetic(_) => self
475                .objective
476                .iter()
477                .map(|objective| objective.column.as_str())
478                .collect(),
479        }
480    }
481
482    /// Returns a searcher over `space`, drawing from [`search_seed`] of `root`.
483    ///
484    /// # Errors
485    ///
486    /// Returns [`SearchSpecError`] when [`Self::check`] rejects the spec.
487    pub fn searcher(&self, space: &SearchSpace, root: u64) -> Result<Box<dyn Searcher + Send>, SearchSpecError> {
488        self.check()?;
489        let space = space.clone();
490        let seed = search_seed(root);
491        let budget = self.max_evaluations;
492        let objective = || {
493            self.objective.clone().ok_or(SearchSpecError::MissingObjective {
494                algorithm: self.algorithm.as_str(),
495            })
496        };
497        Ok(match &self.algorithm {
498            SearchAlgorithm::Random => Box::new(RandomSearch::new(space, objective()?, budget, seed)),
499            SearchAlgorithm::HillClimb(settings) => {
500                Box::new(HillClimb::new(space, *settings, objective()?, budget, seed)?)
501            }
502            SearchAlgorithm::Genetic(settings) => {
503                Box::new(GeneticAlgorithm::new(space, *settings, objective()?, budget, seed)?)
504            }
505            SearchAlgorithm::PatternSpaceExploration(settings) => {
506                Box::new(PatternSpaceExploration::new(space, settings.clone(), budget, seed)?)
507            }
508        })
509    }
510}
511
512/// Search method, with the settings specific to that method.
513#[derive(Debug, Clone, PartialEq)]
514pub enum SearchAlgorithm {
515    /// Random search, run by [`RandomSearch`].
516    Random,
517    /// Hill climb with restarts, run by [`HillClimb`].
518    HillClimb(HillClimbSettings),
519    /// Genetic algorithm, run by [`GeneticAlgorithm`].
520    Genetic(GeneticSettings),
521    /// Pattern Space Exploration, run by [`PatternSpaceExploration`].
522    PatternSpaceExploration(PatternSpaceSettings),
523}
524
525impl SearchAlgorithm {
526    /// Returns the algorithm name used in a spec file.
527    pub fn as_str(&self) -> &'static str {
528        match self {
529            Self::Random => "random",
530            Self::HillClimb(_) => "hill_climb",
531            Self::Genetic(_) => "genetic",
532            Self::PatternSpaceExploration(_) => "pse",
533        }
534    }
535}
536
537/// A search spec that cannot run.
538#[derive(Debug, Clone, PartialEq, Eq)]
539pub enum SearchSpecError {
540    /// A budget of 0 evaluations.
541    NoEvaluations,
542    /// A batch size of 0.
543    NoBatch,
544    /// A batch size past [`MAX_CONFIGS`].
545    BatchTooLarge {
546        /// Batch size as given.
547        batch_size: usize,
548    },
549    /// A random search, hill climb or genetic algorithm with no objective.
550    MissingObjective {
551        /// Name of the algorithm in a spec file, as in `hill_climb`.
552        algorithm: &'static str,
553    },
554    /// An objective given to a Pattern Space Exploration. Pattern Space Exploration uses no objective.
555    UnusedObjective,
556    /// Setting `key` set to `value`, where it accepts `expected`.
557    Setting {
558        /// Key of the setting under `[search]` in a spec file, as in `genetic.population`.
559        key: &'static str,
560        /// Value of the setting as text, or `none` for a bound left out.
561        value: String,
562        /// Values that the setting accepts, in words.
563        expected: String,
564    },
565}
566
567impl fmt::Display for SearchSpecError {
568    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
569        match self {
570            Self::NoEvaluations => write!(f, "max_evaluations must be at least 1"),
571            Self::NoBatch => write!(f, "batch_size must be at least 1"),
572            Self::BatchTooLarge { batch_size } => {
573                write!(f, "batch_size must be at most {MAX_CONFIGS}, got {batch_size}")
574            }
575            Self::MissingObjective { algorithm } => write!(f, "a {algorithm} search needs an objective"),
576            Self::UnusedObjective => write!(f, "a pse search takes x_axis and y_axis, and no objective"),
577            Self::Setting { key, value, expected } => write!(f, "{key} must be {expected}, got {value}"),
578        }
579    }
580}
581
582impl std::error::Error for SearchSpecError {}
583
584/// Returns an error for setting `key` unless `holds`.
585fn check_setting(
586    holds: bool,
587    key: &'static str,
588    value: impl fmt::Display,
589    expected: impl Into<String>,
590) -> Result<(), SearchSpecError> {
591    if holds {
592        Ok(())
593    } else {
594        Err(SearchSpecError::Setting {
595            key,
596            value: value.to_string(),
597            expected: expected.into(),
598        })
599    }
600}
601
602/// A candidate before it has an id.
603#[derive(Debug, Clone, PartialEq)]
604struct Proposal {
605    genome: Genome,
606    replicate_offset: u64,
607    origin: CandidateOrigin,
608}
609
610impl Proposal {
611    /// Returns a proposal for a first evaluation of `genome`.
612    fn first_evaluation(genome: Genome, origin: CandidateOrigin) -> Self {
613        Self {
614            genome,
615            replicate_offset: 0,
616            origin,
617        }
618    }
619
620    /// Returns a proposal for more replicates of candidate `candidate_id`, whose evaluations `record` holds.
621    fn reevaluation(candidate_id: u64, record: &CandidateRecord) -> Self {
622        Self {
623            genome: record.genome().clone(),
624            replicate_offset: record.replicate_count(),
625            origin: CandidateOrigin::Reevaluation { candidate_id },
626        }
627    }
628}
629
630/// Maximum number of genomes drawn for one proposal while each decodes to a config that some candidate has.
631const MAX_CONFIG_DRAWS: usize = 16;
632
633/// Result of [`draw_config`].
634#[derive(Debug, Clone, PartialEq)]
635enum ConfigDraw {
636    /// A genome whose config no candidate and no proposal has, with its key.
637    New(Genome, ConfigKey),
638    /// Every draw produced a known config. The first draw produced the config of candidate `candidate_id`.
639    Known { candidate_id: u64 },
640    /// Every draw produced a known config. The first draw produced the config of a proposal not yet requested.
641    Proposed,
642}
643
644/// Draws genomes with `draw`, at most [`MAX_CONFIG_DRAWS`] times, until a genome decodes to a config that no
645/// candidate of `config_candidates` and no key of `proposed` has.
646///
647/// `config_candidates` holds the first candidate of each config, by key, and `proposed` the keys of the proposals
648/// not yet requested.
649fn draw_config(
650    space: &SearchSpace,
651    config_candidates: &BTreeMap<ConfigKey, u64>,
652    proposed: &BTreeSet<ConfigKey>,
653    mut draw: impl FnMut() -> Genome,
654) -> ConfigDraw {
655    let mut first = None;
656    for _ in 0..MAX_CONFIG_DRAWS {
657        let genome = draw();
658        let key = space.config_key(&genome);
659        let candidate_id = config_candidates.get(&key).copied();
660        if candidate_id.is_none() && !proposed.contains(&key) {
661            return ConfigDraw::New(genome, key);
662        }
663        first.get_or_insert(candidate_id);
664    }
665    match first.flatten() {
666        Some(candidate_id) => ConfigDraw::Known { candidate_id },
667        None => ConfigDraw::Proposed,
668    }
669}
670
671/// Ids, budget and pending candidates of a searcher.
672#[derive(Debug, Clone, PartialEq)]
673struct CandidateTracker {
674    max_evaluations: u64,
675    /// Number of candidates issued so far, and so the id of the next candidate.
676    issued: u64,
677    /// Number of asks that issued at least one candidate.
678    batches: u64,
679    /// Candidates issued and not yet told, each with the index of its batch.
680    pending: BTreeMap<u64, (Candidate, u64)>,
681}
682
683impl CandidateTracker {
684    fn new(max_evaluations: u64) -> Self {
685        Self {
686            max_evaluations,
687            issued: 0,
688            batches: 0,
689            pending: BTreeMap::new(),
690        }
691    }
692
693    /// Returns the number of candidates that a request for `max` can issue within the budget.
694    fn capacity(&self, max: usize) -> usize {
695        let remaining = self.max_evaluations.saturating_sub(self.issued);
696        usize::try_from(remaining).map_or(max, |remaining| remaining.min(max))
697    }
698
699    /// Returns `proposals` as the candidates of one batch, numbered from the next id.
700    fn issue(&mut self, proposals: Vec<Proposal>) -> Vec<Candidate> {
701        if proposals.is_empty() {
702            return Vec::new();
703        }
704        let batch = self.batches;
705        self.batches += 1;
706        proposals
707            .into_iter()
708            .map(|proposal| {
709                let candidate = Candidate {
710                    id: self.issued,
711                    genome: proposal.genome,
712                    replicate_offset: proposal.replicate_offset,
713                    origin: proposal.origin,
714                };
715                self.issued += 1;
716                self.pending.insert(candidate.id, (candidate.clone(), batch));
717                candidate
718            })
719            .collect()
720    }
721
722    /// Removes candidate `candidate_id` from the pending candidates, and returns it with the index of its batch.
723    fn settle(&mut self, candidate_id: u64) -> Option<(Candidate, u64)> {
724        self.pending.remove(&candidate_id)
725    }
726
727    fn is_waiting(&self) -> bool {
728        !self.pending.is_empty()
729    }
730
731    fn is_done(&self) -> bool {
732        self.issued >= self.max_evaluations && self.pending.is_empty()
733    }
734}
henad_core/explore/search/mod.rs

henad_core/explore/search/
mod.rs
