Изменения
Нет описания правки
Цель заключается в минимизации <tex>|f_{\mathcal{I}}^{*}|</tex>.
Необходимо ввести нумерацию элементов <tex>\mathcal{I}</tex>: — <tex>\sigma: \mathcal{I} \rightarrow [n]</tex>. Для любой битовой строки <tex>x \in \{0,1\}^n</tex> определены <tex>\mathcal{I}_0(x) := \{w \in \mathcal{I} | x_{\sigma{(w})} = 0\}</tex> и <tex>\mathcal{I}_1(x) := \{w \in \mathcal{I} | x_{\sigma{(w})} = 1\}</tex>. Тогда ''fitness''-функция выглядит так:
:<tex>f_{\mathcal{I}}: \{0,1\}^n \rightarrow \mathbb{Z}, x \mapsto \Sigma_{i \in [n], x_i=0} \sigma^{-1}(i) - \Sigma_{i \in [n], x_i=1} \sigma^{-1}(i)</tex>.
11 '''else''' <tex>\mathcal{I}_1' \leftarrow \mathcal{I}_1' \cup {|f(x^{(0)}) - f(x^{(t)})|/2}</tex>;
12 '''Оптимизация'''
13 В оффлайне перебором вычисляется оптимальное решение <tex>(\mathcal{O}_0, \mathcal{O}_1)</tex> и множество <tex>\mathcal{M} \leftarrow \{w \in \mathcal{O}_0 | w \notin \mathcal{I}_0'\} \cup \{w \in \mathcal{O}_1 | w \notin \mathcal{I}_1'\}</tex> — множество элементов, которые необходимо переместить.
14 <tex>z \leftarrow x^{(0)}</tex>;
15 '''while''' <tex>|\mathcal{M}| > 0</tex> '''do'''
13 <tex>x^{(2,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(2,t)})</tex>;
14 '''Оптимизация'''
15 Вычисление в В оффлайне перебороим оптимального решения перебором вычисляется оптимальное решение <tex>(\mathcal{O}_0, \mathcal{O}_1)</tex>, такого такое что <tex>w_{max} \in \mathcal{O}_1</tex>. <tex>\mathcal{M} \leftarrow \mathcal{O}_1</tex>;
16 '''for''' <tex>t = 1</tex> '''to''' <tex>2n \log(n)</tex> '''do'''
17 <tex>x^{(3,t)} \leftarrow RLS(x)</tex>. Запрос <tex>f(x^{(3,t)})</tex>;
