Coverage for moptipy / examples / bitstrings / plateau.py: 79%

1""" 

2The Plateau problem. 

3 

4The plateau problem is basically OneMax, but with a neutral region of `k` bit 

5flips before the optimum. The best objective value, 0, is reached if all bits 

6are `True`. The worst objective value `n`, is reached if all bits are `False`. 

7 

81. Denis Antipov and Benjamin Doerr. Precise Runtime Analysis for Plateaus. 

9 Parallel Problem Solving from Nature (PPSN XV), 2018, Part II. LNCS 11102, 

10 pp. 117-128. 

11 doi: https://doi.org/10.1007/978-3-319-99259-4_10 

122. Thomas Weise, Zhize Wu, Xinlu Li, and Yan Chen. Frequency Fitness 

13 Assignment: Making Optimization Algorithms Invariant under Bijective 

14 Transformations of the Objective Function Value. *IEEE Transactions on 

15 Evolutionary Computation* 25(2):307-319. April 2021. Preprint available at 

16 arXiv:2001.01416v5 [cs.NE] 15 Oct 2020. 

17 https://dx.doi.org/10.1109/TEVC.2020.3032090 

183. Thomas Weise, Zhize Wu, Xinlu Li, Yan Chen, and Jörg Lässig. Frequency 

19 Fitness Assignment: Optimization without Bias for Good Solutions can be 

20 Efficient. *IEEE Transactions on Evolutionary Computation (TEVC)*. 

21 27(4):980-992. August 2023. 

22 doi: https://doi.org/10.1109/TEVC.2022.3191698 

23 

24This is code is part of the research work of Mr. Jiazheng ZENG (曾嘉政), 

25a Master's student at the Institute of Applied Optimization 

26(应用优化研究所) of the School of Artificial 

27Intelligence and Big Data (人工智能与大数据学院) at 

28Hefei University (合肥大学) in 

29Hefei, Anhui, China (中国安徽省合肥市) under the supervision of 

30Prof. Dr. Thomas Weise (汤卫思教授). 

31 

32>>> len(list(Plateau.default_instances())) 

33122 

34 

35>>> [x() for x in Plateau.default_instances()] 

36[plateau_6_2, plateau_7_2, plateau_8_2, plateau_8_3, plateau_9_2, \ 

37plateau_9_3, plateau_10_2, plateau_10_3, plateau_10_4, plateau_11_2, \ 

38plateau_11_3, plateau_11_4, plateau_12_2, plateau_12_3, plateau_12_4, \ 

39plateau_12_5, plateau_13_2, plateau_13_3, plateau_13_4, plateau_13_5, \ 

40plateau_14_2, plateau_14_3, plateau_14_4, plateau_14_6, plateau_15_2, \ 

41plateau_15_3, plateau_15_4, plateau_15_6, plateau_16_2, plateau_16_4, \ 

42plateau_16_5, plateau_16_7, plateau_17_2, plateau_17_4, plateau_17_5, \ 

43plateau_17_7, plateau_18_2, plateau_18_4, plateau_18_6, plateau_18_8, \ 

44plateau_19_2, plateau_19_4, plateau_19_6, plateau_19_8, plateau_20_2, \ 

45plateau_20_3, plateau_20_4, plateau_20_5, plateau_20_7, plateau_20_9, \ 

46plateau_21_2, plateau_21_3, plateau_21_4, plateau_21_5, plateau_21_7, \ 

47plateau_21_9, plateau_22_2, plateau_22_3, plateau_22_4, plateau_22_5, \ 

48plateau_22_7, plateau_22_10, plateau_23_2, plateau_23_3, plateau_23_4, \ 

49plateau_23_5, plateau_23_7, plateau_23_10, plateau_24_2, plateau_24_3, \ 

50plateau_24_4, plateau_24_6, plateau_24_8, plateau_24_11, plateau_25_2, \ 

51plateau_25_3, plateau_25_5, plateau_25_6, plateau_25_8, plateau_25_11, \ 

52plateau_26_2, plateau_26_3, plateau_26_5, plateau_26_6, plateau_26_9, \ 

53plateau_26_12, plateau_27_2, plateau_27_3, plateau_27_5, plateau_27_6, \ 

54plateau_27_9, plateau_27_12, plateau_28_2, plateau_28_4, plateau_28_5, \ 

55plateau_28_7, plateau_28_10, plateau_28_13, plateau_29_2, plateau_29_4, \ 

56plateau_29_5, plateau_29_7, plateau_29_10, plateau_29_13, plateau_30_2, \ 

57plateau_30_4, plateau_30_5, plateau_30_7, plateau_30_10, plateau_30_14, \ 

58plateau_31_2, plateau_31_4, plateau_31_5, plateau_31_7, plateau_31_10, \ 

59plateau_31_14, plateau_32_2, plateau_32_4, plateau_32_5, plateau_32_8, \ 

60plateau_32_11, plateau_32_15] 

61""" 

62 

63from typing import Final 

64 

65import numba # type: ignore 

66import numpy as np 

67 

68from moptipy.examples.bitstrings.bitstring_problem import BitStringNKProblem 

69 

70 

71@numba.njit(nogil=True, cache=True) 

72def plateau(x: np.ndarray, k: int) -> int: 

73 """ 

74 Compute the plateau value. 

75 

76 :param x: the np array 

77 :param k: the k parameter 

78 :return: plateau value 

79 

80 # n = 6, k = 2, and 0 true bits 

81 >>> plateau(np.array([0, 0, 0, 0, 0, 0]), 2) 

82 6 

83 

84 # n = 6, k = 2, and 1 true bit 

85 >>> plateau(np.array([0, 0, 0, 1, 0, 0]), 2) 

86 5 

87 

88 # n = 6, k = 2, and 2 true bits 

89 >>> plateau(np.array([0, 0, 1, 0, 1, 0]), 2) 

90 4 

91 

92 # n = 6, k = 2, and 3 true bits 

93 >>> plateau(np.array([1, 1, 1, 0, 0, 0]), 2) 

94 3 

95 

96 # n = 6, k = 2, and 4 true bits 

97 >>> plateau(np.array([1, 1, 1, 1, 0, 0]), 2) 

98 2 

99 

100 # n = 6, k = 2, and 5 true bits 

101 >>> plateau(np.array([1, 1, 1, 1, 1, 0]), 2) 

102 2 

103 

104 # n = 6, k = 2, and 6 true bits 

105 >>> plateau(np.array([1, 1, 1, 1, 1, 1]), 2) 

106 0 

107 

108 # n = 7, k = 2, and 0 true bits 

109 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0]), 2) 

110 7 

111 

112 # n = 7, k = 2, and 1 true bit 

113 >>> plateau(np.array([0, 0, 1, 0, 0, 0, 0]), 2) 

114 6 

115 

116 # n = 7, k = 2, and 2 true bits 

117 >>> plateau(np.array([0, 1, 0, 1, 0, 0, 0]), 2) 

118 5 

119 

120 # n = 7, k = 2, and 3 true bits 

121 >>> plateau(np.array([0, 1, 0, 0, 1, 0, 1]), 2) 

122 4 

123 

124 # n = 7, k = 2, and 4 true bits 

125 >>> plateau(np.array([1, 0, 0, 0, 1, 1, 1]), 2) 

126 3 

127 

128 # n = 7, k = 2, and 5 true bits 

129 >>> plateau(np.array([1, 0, 1, 1, 0, 1, 1]), 2) 

130 2 

131 

132 # n = 7, k = 2, and 6 true bits 

133 >>> plateau(np.array([1, 1, 1, 1, 0, 1, 1]), 2) 

134 2 

135 

136 # n = 7, k = 2, and 7 true bits 

137 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1]), 2) 

138 0 

139 

140 # n = 8, k = 2, and 0 true bits 

141 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0]), 2) 

142 8 

143 

144 # n = 8, k = 2, and 1 true bit 

145 >>> plateau(np.array([0, 1, 0, 0, 0, 0, 0, 0]), 2) 

146 7 

147 

148 # n = 8, k = 2, and 2 true bits 

149 >>> plateau(np.array([1, 0, 0, 0, 1, 0, 0, 0]), 2) 

150 6 

151 

152 # n = 8, k = 2, and 3 true bits 

153 >>> plateau(np.array([0, 0, 0, 1, 0, 1, 0, 1]), 2) 

154 5 

155 

156 # n = 8, k = 2, and 4 true bits 

157 >>> plateau(np.array([0, 0, 0, 1, 1, 1, 0, 1]), 2) 

158 4 

159 

160 # n = 8, k = 2, and 5 true bits 

161 >>> plateau(np.array([1, 1, 0, 1, 1, 0, 0, 1]), 2) 

162 3 

163 

164 # n = 8, k = 2, and 6 true bits 

165 >>> plateau(np.array([0, 0, 1, 1, 1, 1, 1, 1]), 2) 

166 2 

167 

168 # n = 8, k = 2, and 7 true bits 

169 >>> plateau(np.array([1, 1, 1, 1, 1, 0, 1, 1]), 2) 

170 2 

171 

172 # n = 8, k = 2, and 8 true bits 

173 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1]), 2) 

174 0 

175 

176 # n = 8, k = 3, and 0 true bits 

177 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0]), 3) 

178 8 

179 

180 # n = 8, k = 3, and 1 true bit 

181 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 1]), 3) 

182 7 

183 

184 # n = 8, k = 3, and 2 true bits 

185 >>> plateau(np.array([0, 0, 1, 0, 0, 0, 0, 1]), 3) 

186 6 

187 

188 # n = 8, k = 3, and 3 true bits 

189 >>> plateau(np.array([0, 1, 0, 0, 1, 1, 0, 0]), 3) 

190 5 

191 

192 # n = 8, k = 3, and 4 true bits 

193 >>> plateau(np.array([1, 0, 0, 0, 1, 1, 0, 1]), 3) 

194 4 

195 

196 # n = 8, k = 3, and 5 true bits 

197 >>> plateau(np.array([1, 1, 0, 0, 1, 0, 1, 1]), 3) 

198 3 

199 

200 # n = 8, k = 3, and 6 true bits 

201 >>> plateau(np.array([1, 0, 1, 1, 1, 0, 1, 1]), 3) 

202 3 

203 

204 # n = 8, k = 3, and 7 true bits 

205 >>> plateau(np.array([0, 1, 1, 1, 1, 1, 1, 1]), 3) 

206 3 

207 

208 # n = 8, k = 3, and 8 true bits 

209 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1]), 3) 

210 0 

211 

212 # n = 9, k = 2, and 0 true bits 

213 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0]), 2) 

214 9 

215 

216 # n = 9, k = 2, and 1 true bit 

217 >>> plateau(np.array([0, 1, 0, 0, 0, 0, 0, 0, 0]), 2) 

218 8 

219 

220 # n = 9, k = 2, and 2 true bits 

221 >>> plateau(np.array([0, 0, 0, 0, 1, 1, 0, 0, 0]), 2) 

222 7 

223 

224 # n = 9, k = 2, and 3 true bits 

225 >>> plateau(np.array([0, 1, 0, 1, 0, 1, 0, 0, 0]), 2) 

226 6 

227 

228 # n = 9, k = 2, and 4 true bits 

229 >>> plateau(np.array([1, 1, 1, 0, 0, 0, 0, 0, 1]), 2) 

230 5 

231 

232 # n = 9, k = 2, and 5 true bits 

233 >>> plateau(np.array([1, 0, 1, 1, 1, 0, 0, 1, 0]), 2) 

234 4 

235 

236 # n = 9, k = 2, and 6 true bits 

237 >>> plateau(np.array([1, 1, 0, 1, 0, 0, 1, 1, 1]), 2) 

238 3 

239 

240 # n = 9, k = 2, and 7 true bits 

241 >>> plateau(np.array([1, 1, 1, 0, 1, 1, 0, 1, 1]), 2) 

242 2 

243 

244 # n = 9, k = 2, and 8 true bits 

245 >>> plateau(np.array([0, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

246 2 

247 

248 # n = 9, k = 2, and 9 true bits 

249 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

250 0 

251 

252 # n = 9, k = 3, and 0 true bits 

253 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0]), 3) 

254 9 

255 

256 # n = 9, k = 3, and 1 true bit 

257 >>> plateau(np.array([0, 0, 1, 0, 0, 0, 0, 0, 0]), 3) 

258 8 

259 

260 # n = 9, k = 3, and 2 true bits 

261 >>> plateau(np.array([0, 0, 0, 0, 1, 0, 1, 0, 0]), 3) 

262 7 

263 

264 # n = 9, k = 3, and 3 true bits 

265 >>> plateau(np.array([0, 0, 0, 0, 1, 0, 0, 1, 1]), 3) 

266 6 

267 

268 # n = 9, k = 3, and 4 true bits 

269 >>> plateau(np.array([0, 1, 1, 0, 0, 1, 0, 0, 1]), 3) 

270 5 

271 

272 # n = 9, k = 3, and 5 true bits 

273 >>> plateau(np.array([1, 1, 0, 1, 1, 1, 0, 0, 0]), 3) 

274 4 

275 

276 # n = 9, k = 3, and 6 true bits 

277 >>> plateau(np.array([0, 1, 1, 0, 1, 1, 1, 1, 0]), 3) 

278 3 

279 

280 # n = 9, k = 3, and 7 true bits 

281 >>> plateau(np.array([1, 1, 1, 0, 1, 1, 1, 1, 0]), 3) 

282 3 

283 

284 # n = 9, k = 3, and 8 true bits 

285 >>> plateau(np.array([1, 1, 0, 1, 1, 1, 1, 1, 1]), 3) 

286 3 

287 

288 # n = 9, k = 3, and 9 true bits 

289 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

290 0 

291 

292 # n = 10, k = 2, and 0 true bits 

293 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 2) 

294 10 

295 

296 # n = 10, k = 2, and 1 true bit 

297 >>> plateau(np.array([0, 0, 0, 1, 0, 0, 0, 0, 0, 0]), 2) 

298 9 

299 

300 # n = 10, k = 2, and 2 true bits 

301 >>> plateau(np.array([1, 1, 0, 0, 0, 0, 0, 0, 0, 0]), 2) 

302 8 

303 

304 # n = 10, k = 2, and 3 true bits 

305 >>> plateau(np.array([0, 0, 0, 1, 0, 1, 0, 0, 0, 1]), 2) 

306 7 

307 

308 # n = 10, k = 2, and 4 true bits 

309 >>> plateau(np.array([0, 1, 0, 0, 0, 1, 0, 0, 1, 1]), 2) 

310 6 

311 

312 # n = 10, k = 2, and 5 true bits 

313 >>> plateau(np.array([0, 0, 1, 1, 1, 1, 1, 0, 0, 0]), 2) 

314 5 

315 

316 # n = 10, k = 2, and 6 true bits 

317 >>> plateau(np.array([0, 1, 0, 1, 1, 1, 0, 1, 0, 1]), 2) 

318 4 

319 

320 # n = 10, k = 2, and 7 true bits 

321 >>> plateau(np.array([1, 1, 1, 1, 1, 0, 1, 0, 0, 1]), 2) 

322 3 

323 

324 # n = 10, k = 2, and 8 true bits 

325 >>> plateau(np.array([0, 0, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

326 2 

327 

328 # n = 10, k = 2, and 9 true bits 

329 >>> plateau(np.array([1, 0, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

330 2 

331 

332 # n = 10, k = 2, and 10 true bits 

333 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

334 0 

335 

336 # n = 10, k = 3, and 0 true bits 

337 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 3) 

338 10 

339 

340 # n = 10, k = 3, and 1 true bit 

341 >>> plateau(np.array([0, 0, 1, 0, 0, 0, 0, 0, 0, 0]), 3) 

342 9 

343 

344 # n = 10, k = 3, and 2 true bits 

345 >>> plateau(np.array([0, 0, 0, 0, 0, 1, 1, 0, 0, 0]), 3) 

346 8 

347 

348 # n = 10, k = 3, and 3 true bits 

349 >>> plateau(np.array([0, 0, 1, 0, 0, 1, 0, 0, 1, 0]), 3) 

350 7 

351 

352 # n = 10, k = 3, and 4 true bits 

353 >>> plateau(np.array([1, 1, 0, 1, 1, 0, 0, 0, 0, 0]), 3) 

354 6 

355 

356 # n = 10, k = 3, and 5 true bits 

357 >>> plateau(np.array([1, 1, 1, 0, 0, 0, 1, 0, 1, 0]), 3) 

358 5 

359 

360 # n = 10, k = 3, and 6 true bits 

361 >>> plateau(np.array([1, 1, 0, 0, 1, 1, 1, 0, 0, 1]), 3) 

362 4 

363 

364 # n = 10, k = 3, and 7 true bits 

365 >>> plateau(np.array([0, 1, 0, 1, 1, 1, 1, 0, 1, 1]), 3) 

366 3 

367 

368 # n = 10, k = 3, and 8 true bits 

369 >>> plateau(np.array([0, 1, 1, 0, 1, 1, 1, 1, 1, 1]), 3) 

370 3 

371 

372 # n = 10, k = 3, and 9 true bits 

373 >>> plateau(np.array([1, 1, 1, 0, 1, 1, 1, 1, 1, 1]), 3) 

374 3 

375 

376 # n = 10, k = 3, and 10 true bits 

377 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

378 0 

379 

380 # n = 10, k = 4, and 0 true bits 

381 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 4) 

382 10 

383 

384 # n = 10, k = 4, and 1 true bit 

385 >>> plateau(np.array([0, 0, 0, 0, 1, 0, 0, 0, 0, 0]), 4) 

386 9 

387 

388 # n = 10, k = 4, and 2 true bits 

389 >>> plateau(np.array([0, 0, 0, 0, 1, 0, 0, 0, 0, 1]), 4) 

390 8 

391 

392 # n = 10, k = 4, and 3 true bits 

393 >>> plateau(np.array([0, 1, 0, 1, 0, 1, 0, 0, 0, 0]), 4) 

394 7 

395 

396 # n = 10, k = 4, and 4 true bits 

397 >>> plateau(np.array([0, 0, 1, 1, 0, 0, 0, 0, 1, 1]), 4) 

398 6 

399 

400 # n = 10, k = 4, and 5 true bits 

401 >>> plateau(np.array([0, 1, 0, 1, 1, 0, 0, 1, 1, 0]), 4) 

402 5 

403 

404 # n = 10, k = 4, and 6 true bits 

405 >>> plateau(np.array([1, 1, 1, 1, 1, 0, 0, 0, 1, 0]), 4) 

406 4 

407 

408 # n = 10, k = 4, and 7 true bits 

409 >>> plateau(np.array([1, 1, 1, 1, 0, 1, 0, 1, 1, 0]), 4) 

410 4 

411 

412 # n = 10, k = 4, and 8 true bits 

413 >>> plateau(np.array([1, 1, 1, 1, 0, 0, 1, 1, 1, 1]), 4) 

414 4 

415 

416 # n = 10, k = 4, and 9 true bits 

417 >>> plateau(np.array([0, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 4) 

418 4 

419 

420 # n = 10, k = 4, and 10 true bits 

421 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 4) 

422 0 

423 

424 # n = 11, k = 2, and 0 true bits 

425 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 2) 

426 11 

427 

428 # n = 11, k = 2, and 1 true bit 

429 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]), 2) 

430 10 

431 

432 # n = 11, k = 2, and 2 true bits 

433 >>> plateau(np.array([0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0]), 2) 

434 9 

435 

436 # n = 11, k = 2, and 3 true bits 

437 >>> plateau(np.array([1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]), 2) 

438 8 

439 

440 # n = 11, k = 2, and 4 true bits 

441 >>> plateau(np.array([0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1]), 2) 

442 7 

443 

444 # n = 11, k = 2, and 5 true bits 

445 >>> plateau(np.array([0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1]), 2) 

446 6 

447 

448 # n = 11, k = 2, and 6 true bits 

449 >>> plateau(np.array([0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0]), 2) 

450 5 

451 

452 # n = 11, k = 2, and 7 true bits 

453 >>> plateau(np.array([0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0]), 2) 

454 4 

455 

456 # n = 11, k = 2, and 8 true bits 

457 >>> plateau(np.array([1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0]), 2) 

458 3 

459 

460 # n = 11, k = 2, and 9 true bits 

461 >>> plateau(np.array([0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]), 2) 

462 2 

463 

464 # n = 11, k = 2, and 10 true bits 

465 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]), 2) 

466 2 

467 

468 # n = 11, k = 2, and 11 true bits 

469 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

470 0 

471 

472 # n = 11, k = 3, and 0 true bits 

473 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 3) 

474 11 

475 

476 # n = 11, k = 3, and 1 true bit 

477 >>> plateau(np.array([0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]), 3) 

478 10 

479 

480 # n = 11, k = 3, and 2 true bits 

481 >>> plateau(np.array([0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1]), 3) 

482 9 

483 

484 # n = 11, k = 3, and 3 true bits 

485 >>> plateau(np.array([0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1]), 3) 

486 8 

487 

488 # n = 11, k = 3, and 4 true bits 

489 >>> plateau(np.array([0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1]), 3) 

490 7 

491 

492 # n = 11, k = 3, and 5 true bits 

493 >>> plateau(np.array([0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1]), 3) 

494 6 

495 

496 # n = 11, k = 3, and 6 true bits 

497 >>> plateau(np.array([0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0]), 3) 

498 5 

499 

500 # n = 11, k = 3, and 7 true bits 

501 >>> plateau(np.array([1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0]), 3) 

502 4 

503 

504 # n = 11, k = 3, and 8 true bits 

505 >>> plateau(np.array([1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0]), 3) 

506 3 

507 

508 # n = 11, k = 3, and 9 true bits 

509 >>> plateau(np.array([0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

510 3 

511 

512 # n = 11, k = 3, and 10 true bits 

513 >>> plateau(np.array([0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

514 3 

515 

516 # n = 11, k = 3, and 11 true bits 

517 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

518 0 

519 

520 # n = 11, k = 4, and 0 true bits 

521 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 4) 

522 11 

523 

524 # n = 11, k = 4, and 1 true bit 

525 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]), 4) 

526 10 

527 

528 # n = 11, k = 4, and 2 true bits 

529 >>> plateau(np.array([0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0]), 4) 

530 9 

531 

532 # n = 11, k = 4, and 3 true bits 

533 >>> plateau(np.array([0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0]), 4) 

534 8 

535 

536 # n = 11, k = 4, and 4 true bits 

537 >>> plateau(np.array([0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0]), 4) 

538 7 

539 

540 # n = 11, k = 4, and 5 true bits 

541 >>> plateau(np.array([0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1]), 4) 

542 6 

543 

544 # n = 11, k = 4, and 6 true bits 

545 >>> plateau(np.array([1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0]), 4) 

546 5 

547 

548 # n = 11, k = 4, and 7 true bits 

549 >>> plateau(np.array([1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0]), 4) 

550 4 

551 

552 # n = 11, k = 4, and 8 true bits 

553 >>> plateau(np.array([0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1]), 4) 

554 4 

555 

556 # n = 11, k = 4, and 9 true bits 

557 >>> plateau(np.array([1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1]), 4) 

558 4 

559 

560 # n = 11, k = 4, and 10 true bits 

561 >>> plateau(np.array([0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 4) 

562 4 

563 

564 # n = 11, k = 4, and 11 true bits 

565 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 4) 

566 0 

567 

568 # n = 12, k = 2, and 0 true bits 

569 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 2) 

570 12 

571 

572 # n = 12, k = 2, and 1 true bit 

573 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]), 2) 

574 11 

575 

576 # n = 12, k = 2, and 2 true bits 

577 >>> plateau(np.array([0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]), 2) 

578 10 

579 

580 # n = 12, k = 2, and 3 true bits 

581 >>> plateau(np.array([1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]), 2) 

582 9 

583 

584 # n = 12, k = 2, and 4 true bits 

585 >>> plateau(np.array([1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0]), 2) 

586 8 

587 

588 # n = 12, k = 2, and 5 true bits 

589 >>> plateau(np.array([1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0]), 2) 

590 7 

591 

592 # n = 12, k = 2, and 6 true bits 

593 >>> plateau(np.array([1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1]), 2) 

594 6 

595 

596 # n = 12, k = 2, and 7 true bits 

597 >>> plateau(np.array([0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1]), 2) 

598 5 

599 

600 # n = 12, k = 2, and 8 true bits 

601 >>> plateau(np.array([0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1]), 2) 

602 4 

603 

604 # n = 12, k = 2, and 9 true bits 

605 >>> plateau(np.array([1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0]), 2) 

606 3 

607 

608 # n = 12, k = 2, and 10 true bits 

609 >>> plateau(np.array([1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1]), 2) 

610 2 

611 

612 # n = 12, k = 2, and 11 true bits 

613 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]), 2) 

614 2 

615 

616 # n = 12, k = 2, and 12 true bits 

617 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

618 0 

619 

620 # n = 12, k = 3, and 0 true bits 

621 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 3) 

622 12 

623 

624 # n = 12, k = 3, and 1 true bit 

625 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]), 3) 

626 11 

627 

628 # n = 12, k = 3, and 2 true bits 

629 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1]), 3) 

630 10 

631 

632 # n = 12, k = 3, and 3 true bits 

633 >>> plateau(np.array([1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0]), 3) 

634 9 

635 

636 # n = 12, k = 3, and 4 true bits 

637 >>> plateau(np.array([0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1]), 3) 

638 8 

639 

640 # n = 12, k = 3, and 5 true bits 

641 >>> plateau(np.array([0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1]), 3) 

642 7 

643 

644 # n = 12, k = 3, and 6 true bits 

645 >>> plateau(np.array([1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1]), 3) 

646 6 

647 

648 # n = 12, k = 3, and 7 true bits 

649 >>> plateau(np.array([1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0]), 3) 

650 5 

651 

652 # n = 12, k = 3, and 8 true bits 

653 >>> plateau(np.array([0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0]), 3) 

654 4 

655 

656 # n = 12, k = 3, and 9 true bits 

657 >>> plateau(np.array([0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1]), 3) 

658 3 

659 

660 # n = 12, k = 3, and 10 true bits 

661 >>> plateau(np.array([0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]), 3) 

662 3 

663 

664 # n = 12, k = 3, and 11 true bits 

665 >>> plateau(np.array([1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

666 3 

667 

668 # n = 12, k = 3, and 12 true bits 

669 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

670 0 

671 

672 # n = 12, k = 4, and 0 true bits 

673 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 4) 

674 12 

675 

676 # n = 12, k = 4, and 1 true bit 

677 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]), 4) 

678 11 

679 

680 # n = 12, k = 4, and 2 true bits 

681 >>> plateau(np.array([0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]), 4) 

682 10 

683 

684 # n = 12, k = 4, and 3 true bits 

685 >>> plateau(np.array([0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0]), 4) 

686 9 

687 

688 # n = 12, k = 4, and 4 true bits 

689 >>> plateau(np.array([1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0]), 4) 

690 8 

691 

692 # n = 12, k = 4, and 5 true bits 

693 >>> plateau(np.array([1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0]), 4) 

694 7 

695 

696 # n = 12, k = 4, and 6 true bits 

697 >>> plateau(np.array([0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0]), 4) 

698 6 

699 

700 # n = 12, k = 4, and 7 true bits 

701 >>> plateau(np.array([1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0]), 4) 

702 5 

703 

704 # n = 12, k = 4, and 8 true bits 

705 >>> plateau(np.array([1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0]), 4) 

706 4 

707 

708 # n = 12, k = 4, and 9 true bits 

709 >>> plateau(np.array([1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1]), 4) 

710 4 

711 

712 # n = 12, k = 4, and 10 true bits 

713 >>> plateau(np.array([1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]), 4) 

714 4 

715 

716 # n = 12, k = 4, and 11 true bits 

717 >>> plateau(np.array([1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]), 4) 

718 4 

719 

720 # n = 12, k = 4, and 12 true bits 

721 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 4) 

722 0 

723 

724 # n = 12, k = 5, and 0 true bits 

725 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 5) 

726 12 

727 

728 # n = 12, k = 5, and 1 true bit 

729 >>> plateau(np.array([0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]), 5) 

730 11 

731 

732 # n = 12, k = 5, and 2 true bits 

733 >>> plateau(np.array([0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0]), 5) 

734 10 

735 

736 # n = 12, k = 5, and 3 true bits 

737 >>> plateau(np.array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]), 5) 

738 9 

739 

740 # n = 12, k = 5, and 4 true bits 

741 >>> plateau(np.array([0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1]), 5) 

742 8 

743 

744 # n = 12, k = 5, and 5 true bits 

745 >>> plateau(np.array([0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1]), 5) 

746 7 

747 

748 # n = 12, k = 5, and 6 true bits 

749 >>> plateau(np.array([1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0]), 5) 

750 6 

751 

752 # n = 12, k = 5, and 7 true bits 

753 >>> plateau(np.array([0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1]), 5) 

754 5 

755 

756 # n = 12, k = 5, and 8 true bits 

757 >>> plateau(np.array([1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0]), 5) 

758 5 

759 

760 # n = 12, k = 5, and 9 true bits 

761 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1]), 5) 

762 5 

763 

764 # n = 12, k = 5, and 10 true bits 

765 >>> plateau(np.array([1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1]), 5) 

766 5 

767 

768 # n = 12, k = 5, and 11 true bits 

769 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]), 5) 

770 5 

771 

772 # n = 12, k = 5, and 12 true bits 

773 >>> plateau(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 5) 

774 0 

775 """ 

776 res: Final[int] = int(x.sum()) 

777 n: Final[int] = len(x) 

778 return 0 if res >= n else n - res if res <= (n - k) else k 

779 

780 

781class Plateau(BitStringNKProblem): 

782 """Compute the Plateau problem.""" 

783 

784 def __str__(self) -> str: 

785 """ 

786 Get the name of the plateau objective function. 

787 

788 :return: `plateau_` + length of string + `_` + k 

789 

790 >>> Plateau(13, 4) 

791 plateau_13_4 

792 """ 

793 return f"plateau_{self.n}_{self.k}" 

794 

795 def evaluate(self, x: np.ndarray) -> int: 

796 """ 

797 Evaluate a solution to the plateau problem. 

798 

799 :param x: the bit string to evaluate 

800 :returns: the value of the plateau problem for the string 

801 """ 

802 return plateau(x, self.k)