Coverage for moptipy / examples / bitstrings / jump.py: 76%

1""" 

2The Jump problem. 

3 

4The Jump problem is basically OneMax, but with a deceptive region of `k` bit 

5flips before the optimum. 

6The optimal objective value is 0, which is reached if all bits are `True`. 

7The worst objective value is `n + k - 1`, which is reached if exactly one 

8bit is `False`. 

9 

101. Stefan Droste, Thomas Jansen, and Ingo Wegener. On the Analysis of the 

11 (1+1) Evolutionary Algorithm. *Theoretical Computer Science.* 

12 276(1-2):51-81. April 2002. 

13 doi: https://doi.org/10.1016/S0304-3975(01)00182-7 

142. Tobias Friedrich, Francesco Quinzan, and Markus Wagner. Escaping Large 

15 Deceptive Basins of Attraction with Heavy-Tailed Mutation Operators. In 

16 Hernán E. Aguirre and Keiki Takadama, editors, *Proceedings of the Genetic 

17 and Evolutionary Computation Conference (GECCO'18),* July 15-19, 2018. 

18 Kyoto, Japan. ACM. doi: https://doi.org/10.1145/3205455.3205515} 

193. Francesco Quinzan, Andreas Göbel, Markus Wagner, and Tobias Friedrich. 

20 Evolutionary algorithms and submodular functions: benefits of heavy-tailed 

21 mutations. *Natural Computing.* 20(3):561-575. September 2021. 

22 doi: https://doi.org/10.1007/s11047-021-09841-7. 

23 Also: arXiv:1805.10902v2 [cs.DS] 21 Nov 2018. 

24 https://arxiv.org/abs/1805.10902 

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

26 Assignment: Making Optimization Algorithms Invariant under Bijective 

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

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

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

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

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

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

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

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

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

36 

37>>> len(list(Jump.default_instances())) 

38122 

39 

40>>> [x() for x in Jump.default_instances()] 

41[jump_6_2, jump_7_2, jump_8_2, jump_8_3, jump_9_2, jump_9_3, jump_10_2, \ 

42jump_10_3, jump_10_4, jump_11_2, jump_11_3, jump_11_4, jump_12_2, jump_12_3, \ 

43jump_12_4, jump_12_5, jump_13_2, jump_13_3, jump_13_4, jump_13_5, jump_14_2, \ 

44jump_14_3, jump_14_4, jump_14_6, jump_15_2, jump_15_3, jump_15_4, jump_15_6, \ 

45jump_16_2, jump_16_4, jump_16_5, jump_16_7, jump_17_2, jump_17_4, jump_17_5, \ 

46jump_17_7, jump_18_2, jump_18_4, jump_18_6, jump_18_8, jump_19_2, jump_19_4, \ 

47jump_19_6, jump_19_8, jump_20_2, jump_20_3, jump_20_4, jump_20_5, jump_20_7, \ 

48jump_20_9, jump_21_2, jump_21_3, jump_21_4, jump_21_5, jump_21_7, jump_21_9, \ 

49jump_22_2, jump_22_3, jump_22_4, jump_22_5, jump_22_7, jump_22_10, \ 

50jump_23_2, jump_23_3, jump_23_4, jump_23_5, jump_23_7, jump_23_10, \ 

51jump_24_2, jump_24_3, jump_24_4, jump_24_6, jump_24_8, jump_24_11, \ 

52jump_25_2, jump_25_3, jump_25_5, jump_25_6, jump_25_8, jump_25_11, \ 

53jump_26_2, jump_26_3, jump_26_5, jump_26_6, jump_26_9, jump_26_12, \ 

54jump_27_2, jump_27_3, jump_27_5, jump_27_6, jump_27_9, jump_27_12, \ 

55jump_28_2, jump_28_4, jump_28_5, jump_28_7, jump_28_10, jump_28_13, \ 

56jump_29_2, jump_29_4, jump_29_5, jump_29_7, jump_29_10, jump_29_13, \ 

57jump_30_2, jump_30_4, jump_30_5, jump_30_7, jump_30_10, jump_30_14, \ 

58jump_31_2, jump_31_4, jump_31_5, jump_31_7, jump_31_10, jump_31_14, \ 

59jump_32_2, jump_32_4, jump_32_5, jump_32_8, jump_32_11, jump_32_15] 

60""" 

61 

62from typing import Final 

63 

64import numba # type: ignore 

65import numpy as np 

66 

67from moptipy.examples.bitstrings.bitstring_problem import BitStringNKProblem 

68 

69 

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

71def jump(x: np.ndarray, k: int) -> int: 

72 """ 

73 Compute the jump value. 

74 

75 :param x: the np array 

76 :param k: the k parameter 

77 :return: jump value 

78 

79 >>> jump(np.array([False, False, False, False, False, False]), 2) 

80 6 

81 >>> jump(np.array([False, False, False, False, True, False]), 2) 

82 5 

83 >>> jump(np.array([False, True, True, False, False, False]), 2) 

84 4 

85 >>> jump(np.array([True, False, True, False, True, False]), 2) 

86 3 

87 >>> jump(np.array([True, False, True, False, True, True]), 2) 

88 2 

89 >>> jump(np.array([True, True, True, True, True, False]), 2) 

90 7 

91 >>> jump(np.array([True, True, True, True, True, True]), 2) 

92 0 

93 

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

95 >>> jump(np.array([0, 0, 0, 0, 0, 0]), 2) 

96 6 

97 

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

99 >>> jump(np.array([0, 0, 0, 1, 0, 0]), 2) 

100 5 

101 

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

103 >>> jump(np.array([0, 0, 1, 0, 0, 1]), 2) 

104 4 

105 

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

107 >>> jump(np.array([1, 1, 1, 0, 0, 0]), 2) 

108 3 

109 

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

111 >>> jump(np.array([1, 0, 0, 1, 1, 1]), 2) 

112 2 

113 

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

115 >>> jump(np.array([1, 1, 1, 1, 0, 1]), 2) 

116 7 

117 

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

119 >>> jump(np.array([1, 1, 1, 1, 1, 1]), 2) 

120 0 

121 

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

123 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0]), 2) 

124 7 

125 

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

127 >>> jump(np.array([0, 0, 0, 1, 0, 0, 0]), 2) 

128 6 

129 

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

131 >>> jump(np.array([0, 0, 1, 0, 1, 0, 0]), 2) 

132 5 

133 

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

135 >>> jump(np.array([1, 1, 0, 1, 0, 0, 0]), 2) 

136 4 

137 

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

139 >>> jump(np.array([0, 1, 0, 1, 1, 1, 0]), 2) 

140 3 

141 

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

143 >>> jump(np.array([1, 0, 1, 1, 0, 1, 1]), 2) 

144 2 

145 

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

147 >>> jump(np.array([1, 1, 1, 1, 0, 1, 1]), 2) 

148 8 

149 

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

151 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1]), 2) 

152 0 

153 

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

155 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0]), 2) 

156 8 

157 

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

159 >>> jump(np.array([0, 0, 0, 0, 0, 0, 1, 0]), 2) 

160 7 

161 

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

163 >>> jump(np.array([0, 0, 0, 0, 0, 0, 1, 1]), 2) 

164 6 

165 

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

167 >>> jump(np.array([0, 0, 1, 0, 0, 0, 1, 1]), 2) 

168 5 

169 

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

171 >>> jump(np.array([0, 0, 0, 1, 1, 1, 0, 1]), 2) 

172 4 

173 

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

175 >>> jump(np.array([0, 1, 1, 1, 1, 1, 0, 0]), 2) 

176 3 

177 

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

179 >>> jump(np.array([1, 1, 1, 0, 1, 1, 1, 0]), 2) 

180 2 

181 

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

183 >>> jump(np.array([1, 1, 1, 1, 0, 1, 1, 1]), 2) 

184 9 

185 

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

187 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1]), 2) 

188 0 

189 

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

191 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0]), 3) 

192 8 

193 

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

195 >>> jump(np.array([0, 1, 0, 0, 0, 0, 0, 0]), 3) 

196 7 

197 

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

199 >>> jump(np.array([0, 0, 0, 0, 1, 0, 0, 1]), 3) 

200 6 

201 

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

203 >>> jump(np.array([0, 0, 0, 1, 1, 1, 0, 0]), 3) 

204 5 

205 

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

207 >>> jump(np.array([0, 1, 0, 0, 1, 1, 1, 0]), 3) 

208 4 

209 

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

211 >>> jump(np.array([1, 0, 1, 1, 1, 0, 0, 1]), 3) 

212 3 

213 

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

215 >>> jump(np.array([1, 0, 1, 0, 1, 1, 1, 1]), 3) 

216 9 

217 

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

219 >>> jump(np.array([1, 0, 1, 1, 1, 1, 1, 1]), 3) 

220 10 

221 

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

223 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1]), 3) 

224 0 

225 

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

227 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0]), 2) 

228 9 

229 

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

231 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 1]), 2) 

232 8 

233 

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

235 >>> jump(np.array([0, 0, 1, 0, 0, 0, 0, 0, 1]), 2) 

236 7 

237 

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

239 >>> jump(np.array([0, 0, 0, 1, 0, 0, 1, 0, 1]), 2) 

240 6 

241 

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

243 >>> jump(np.array([1, 0, 0, 0, 1, 0, 0, 1, 1]), 2) 

244 5 

245 

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

247 >>> jump(np.array([0, 0, 0, 1, 1, 0, 1, 1, 1]), 2) 

248 4 

249 

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

251 >>> jump(np.array([1, 1, 0, 1, 0, 1, 1, 1, 0]), 2) 

252 3 

253 

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

255 >>> jump(np.array([1, 0, 1, 1, 1, 1, 0, 1, 1]), 2) 

256 2 

257 

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

259 >>> jump(np.array([1, 1, 1, 1, 1, 0, 1, 1, 1]), 2) 

260 10 

261 

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

263 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

264 0 

265 

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

267 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0]), 3) 

268 9 

269 

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

271 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 1]), 3) 

272 8 

273 

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

275 >>> jump(np.array([0, 0, 1, 0, 1, 0, 0, 0, 0]), 3) 

276 7 

277 

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

279 >>> jump(np.array([0, 1, 0, 1, 1, 0, 0, 0, 0]), 3) 

280 6 

281 

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

283 >>> jump(np.array([0, 1, 1, 0, 1, 0, 0, 1, 0]), 3) 

284 5 

285 

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

287 >>> jump(np.array([1, 1, 1, 1, 0, 0, 0, 0, 1]), 3) 

288 4 

289 

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

291 >>> jump(np.array([0, 0, 1, 1, 1, 1, 1, 0, 1]), 3) 

292 3 

293 

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

295 >>> jump(np.array([0, 1, 1, 1, 1, 1, 1, 1, 0]), 3) 

296 10 

297 

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

299 >>> jump(np.array([0, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

300 11 

301 

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

303 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

304 0 

305 

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

307 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 2) 

308 10 

309 

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

311 >>> jump(np.array([0, 0, 0, 0, 0, 1, 0, 0, 0, 0]), 2) 

312 9 

313 

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

315 >>> jump(np.array([0, 0, 1, 0, 0, 0, 0, 0, 0, 1]), 2) 

316 8 

317 

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

319 >>> jump(np.array([0, 1, 0, 0, 1, 0, 0, 0, 0, 1]), 2) 

320 7 

321 

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

323 >>> jump(np.array([0, 0, 1, 0, 1, 0, 1, 0, 0, 1]), 2) 

324 6 

325 

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

327 >>> jump(np.array([1, 0, 1, 1, 0, 1, 1, 0, 0, 0]), 2) 

328 5 

329 

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

331 >>> jump(np.array([1, 1, 0, 1, 1, 0, 0, 0, 1, 1]), 2) 

332 4 

333 

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

335 >>> jump(np.array([1, 0, 1, 0, 1, 0, 1, 1, 1, 1]), 2) 

336 3 

337 

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

339 >>> jump(np.array([1, 0, 1, 1, 1, 1, 1, 0, 1, 1]), 2) 

340 2 

341 

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

343 >>> jump(np.array([1, 0, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

344 11 

345 

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

347 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

348 0 

349 

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

351 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 3) 

352 10 

353 

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

355 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 1, 0]), 3) 

356 9 

357 

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

359 >>> jump(np.array([1, 0, 0, 0, 0, 0, 1, 0, 0, 0]), 3) 

360 8 

361 

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

363 >>> jump(np.array([0, 1, 0, 1, 0, 0, 1, 0, 0, 0]), 3) 

364 7 

365 

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

367 >>> jump(np.array([0, 0, 1, 0, 1, 1, 0, 0, 1, 0]), 3) 

368 6 

369 

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

371 >>> jump(np.array([0, 0, 1, 1, 0, 0, 1, 1, 0, 1]), 3) 

372 5 

373 

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

375 >>> jump(np.array([1, 0, 0, 1, 1, 1, 0, 1, 0, 1]), 3) 

376 4 

377 

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

379 >>> jump(np.array([0, 1, 1, 1, 1, 1, 0, 0, 1, 1]), 3) 

380 3 

381 

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

383 >>> jump(np.array([0, 1, 1, 1, 1, 1, 1, 0, 1, 1]), 3) 

384 11 

385 

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

387 >>> jump(np.array([1, 1, 0, 1, 1, 1, 1, 1, 1, 1]), 3) 

388 12 

389 

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

391 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

392 0 

393 

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

395 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 4) 

396 10 

397 

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

399 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 1]), 4) 

400 9 

401 

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

403 >>> jump(np.array([0, 1, 0, 0, 0, 0, 0, 0, 1, 0]), 4) 

404 8 

405 

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

407 >>> jump(np.array([1, 0, 1, 0, 0, 1, 0, 0, 0, 0]), 4) 

408 7 

409 

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

411 >>> jump(np.array([0, 0, 0, 0, 0, 1, 1, 0, 1, 1]), 4) 

412 6 

413 

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

415 >>> jump(np.array([0, 1, 1, 0, 1, 0, 1, 0, 1, 0]), 4) 

416 5 

417 

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

419 >>> jump(np.array([1, 1, 1, 1, 0, 1, 0, 0, 1, 0]), 4) 

420 4 

421 

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

423 >>> jump(np.array([0, 1, 1, 1, 0, 1, 1, 1, 1, 0]), 4) 

424 11 

425 

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

427 >>> jump(np.array([1, 0, 1, 1, 1, 0, 1, 1, 1, 1]), 4) 

428 12 

429 

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

431 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 0, 1, 1]), 4) 

432 13 

433 

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

435 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 4) 

436 0 

437 

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

439 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 2) 

440 11 

441 

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

443 >>> jump(np.array([0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]), 2) 

444 10 

445 

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

447 >>> jump(np.array([0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]), 2) 

448 9 

449 

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

451 >>> jump(np.array([0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0]), 2) 

452 8 

453 

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

455 >>> jump(np.array([1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0]), 2) 

456 7 

457 

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

459 >>> jump(np.array([1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1]), 2) 

460 6 

461 

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

463 >>> jump(np.array([1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0]), 2) 

464 5 

465 

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

467 >>> jump(np.array([1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0]), 2) 

468 4 

469 

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

471 >>> jump(np.array([1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0]), 2) 

472 3 

473 

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

475 >>> jump(np.array([0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1]), 2) 

476 2 

477 

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

479 >>> jump(np.array([1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]), 2) 

480 12 

481 

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

483 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

484 0 

485 

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

487 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 3) 

488 11 

489 

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

491 >>> jump(np.array([0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]), 3) 

492 10 

493 

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

495 >>> jump(np.array([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]), 3) 

496 9 

497 

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

499 >>> jump(np.array([0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0]), 3) 

500 8 

501 

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

503 >>> jump(np.array([1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1]), 3) 

504 7 

505 

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

507 >>> jump(np.array([1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0]), 3) 

508 6 

509 

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

511 >>> jump(np.array([0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1]), 3) 

512 5 

513 

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

515 >>> jump(np.array([0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0]), 3) 

516 4 

517 

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

519 >>> jump(np.array([0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1]), 3) 

520 3 

521 

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

523 >>> jump(np.array([1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1]), 3) 

524 12 

525 

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

527 >>> jump(np.array([0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

528 13 

529 

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

531 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

532 0 

533 

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

535 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 4) 

536 11 

537 

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

539 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]), 4) 

540 10 

541 

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

543 >>> jump(np.array([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]), 4) 

544 9 

545 

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

547 >>> jump(np.array([0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1]), 4) 

548 8 

549 

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

551 >>> jump(np.array([1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1]), 4) 

552 7 

553 

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

555 >>> jump(np.array([1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0]), 4) 

556 6 

557 

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

559 >>> jump(np.array([0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1]), 4) 

560 5 

561 

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

563 >>> jump(np.array([1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1]), 4) 

564 4 

565 

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

567 >>> jump(np.array([1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1]), 4) 

568 12 

569 

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

571 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0]), 4) 

572 13 

573 

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

575 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]), 4) 

576 14 

577 

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

579 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 4) 

580 0 

581 

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

583 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 2) 

584 12 

585 

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

587 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]), 2) 

588 11 

589 

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

591 >>> jump(np.array([0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 2) 

592 10 

593 

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

595 >>> jump(np.array([0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0]), 2) 

596 9 

597 

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

599 >>> jump(np.array([1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]), 2) 

600 8 

601 

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

603 >>> jump(np.array([1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1]), 2) 

604 7 

605 

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

607 >>> jump(np.array([1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0]), 2) 

608 6 

609 

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

611 >>> jump(np.array([1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0]), 2) 

612 5 

613 

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

615 >>> jump(np.array([1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1]), 2) 

616 4 

617 

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

619 >>> jump(np.array([1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1]), 2) 

620 3 

621 

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

623 >>> jump(np.array([0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]), 2) 

624 2 

625 

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

627 >>> jump(np.array([0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

628 13 

629 

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

631 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 2) 

632 0 

633 

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

635 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 3) 

636 12 

637 

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

639 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]), 3) 

640 11 

641 

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

643 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0]), 3) 

644 10 

645 

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

647 >>> jump(np.array([1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1]), 3) 

648 9 

649 

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

651 >>> jump(np.array([0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0]), 3) 

652 8 

653 

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

655 >>> jump(np.array([0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0]), 3) 

656 7 

657 

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

659 >>> jump(np.array([0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1]), 3) 

660 6 

661 

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

663 >>> jump(np.array([1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1]), 3) 

664 5 

665 

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

667 >>> jump(np.array([1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1]), 3) 

668 4 

669 

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

671 >>> jump(np.array([1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0]), 3) 

672 3 

673 

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

675 >>> jump(np.array([1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1]), 3) 

676 13 

677 

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

679 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]), 3) 

680 14 

681 

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

683 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 3) 

684 0 

685 

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

687 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 4) 

688 12 

689 

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

691 >>> jump(np.array([0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]), 4) 

692 11 

693 

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

695 >>> jump(np.array([1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]), 4) 

696 10 

697 

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

699 >>> jump(np.array([1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]), 4) 

700 9 

701 

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

703 >>> jump(np.array([1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0]), 4) 

704 8 

705 

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

707 >>> jump(np.array([0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0]), 4) 

708 7 

709 

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

711 >>> jump(np.array([0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0]), 4) 

712 6 

713 

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

715 >>> jump(np.array([1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1]), 4) 

716 5 

717 

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

719 >>> jump(np.array([0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1]), 4) 

720 4 

721 

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

723 >>> jump(np.array([1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1]), 4) 

724 13 

725 

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

727 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0]), 4) 

728 14 

729 

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

731 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]), 4) 

732 15 

733 

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

735 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 4) 

736 0 

737 

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

739 >>> jump(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 5) 

740 12 

741 

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

743 >>> jump(np.array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 5) 

744 11 

745 

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

747 >>> jump(np.array([0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 5) 

748 10 

749 

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

751 >>> jump(np.array([0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0]), 5) 

752 9 

753 

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

755 >>> jump(np.array([0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1]), 5) 

756 8 

757 

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

759 >>> jump(np.array([1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0]), 5) 

760 7 

761 

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

763 >>> jump(np.array([0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0]), 5) 

764 6 

765 

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

767 >>> jump(np.array([1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0]), 5) 

768 5 

769 

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

771 >>> jump(np.array([0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1]), 5) 

772 13 

773 

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

775 >>> jump(np.array([1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1]), 5) 

776 14 

777 

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

779 >>> jump(np.array([1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1]), 5) 

780 15 

781 

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

783 >>> jump(np.array([1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]), 5) 

784 16 

785 

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

787 >>> jump(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 5) 

788 0 

789 """ 

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

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

792 nmk: Final[int] = n - k 

793 return n - res if (res >= n) or (res <= nmk) else k + res 

794 

795 

796class Jump(BitStringNKProblem): 

797 """Compute the Jump problem.""" 

798 

799 def __str__(self) -> str: 

800 """ 

801 Get the name of the jump objective function. 

802 

803 :return: `jump_` + length of string + `_` + k 

804 

805 >>> Jump(13, 4) 

806 jump_13_4 

807 """ 

808 return f"jump_{self.n}_{self.k}" 

809 

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

811 """ 

812 Evaluate a solution to the jump problem. 

813 

814 :param x: the bit string to evaluate 

815 :returns: the value of the jump problem for the string 

816 """ 

817 return jump(x, self.k) 

818 

819 def upper_bound(self) -> int: 

820 """ 

821 Get the upper bound of the jump problem. 

822 

823 :return: the length of the bit string + the length of the jump - 1 

824 

825 >>> Jump(15, 4).upper_bound() 

826 18 

827 """ 

828 return self.n + self.k - 1