2011数学建模B题第一问遗传算法的matlab程序

clear all
clc
x=[413 403 383.5 381 339 335 317 334.5 333 282 247 219 225 280 290 337 415 432 418 444 251 234 225 212 227 256 250.5 243 246 314 315 326 327 328 336 336 331 371 371 388.5 411 419 411 394 342 342 325 315 342 345 348.5 351 348 370 371 354 363 357 351 369 335 381 391 392 395 398 401 405 410 408 415 418 422 418.5 405.5 405 409 417 420 424 438 438.5 434 438 440 447 448 444.5 441 440.5 445 444 140 145 160 142.5 150 186 158 121 157 158 159 133 137.5 144 139 144.5 151 151.5 150 158 159 164 163 149 143 137 131 130 127 125 129 130 124 136 136 142 148 142 147 128 136.5 142 147 154 148.5 140 140 137.5 138 143 151 153 143 143 143 160 162 141 143 151 150 164 171 165.5 181 176 170 168 166 176 180 183 202 137.5 167 376 210 263 284 278.5 295 299 362 410 395 277 235 200 167 225 400 414 424 411 420 403 376 380 377 374 370 368 374 365 356 358 354 357 359 347 261 270 313 324 333 334 323 312 317 316 315.5 316 318 291.5 284 281 299 302 305 281 274 273.5 267 270 275 276 270 276 288 293.5 296 303 298.5 293 296 276 250 247 262 269 276 282 282 273 276 138.5 155 163 173 183 238 213 189 210 201 150 135 143 142 140 121 109 138.5 167 168 184 194 200 212 220 246 246 252 257 255.5 249 247 254 251.5 259 261 255 240 241 236 235 232 235.5 245 225 225 219 219 228.5 213 211 208.5 206 206 200 200 200 200 206 194 184 184 193.5 193 184 184 192.5 192 192 170 168 167 101 91 70 46 56 20 74 76 15 28 34.5 30 27 42 30 31 39 50 72 60 95 81 80 67 21 36 76 97 103 104 97 89 81 81 89 92.5 88 81.5 87 84 76 58.5 34 38 61 57 60 85 107.5 131 170 174 232.5 202 241 235 228 214 278 267 90 123 143 192 145 133 90 21 60 70 27 62 58 58 72 70 90 115 115 123 123 123 143 144 149 128 128 164 156 168 156 167 172 167 160 163 186 269 295 302 316 278 284 257.5 239 241 246 246.5 240 236 231 232 239.5 242 235 237.5 246 200 170 59 72 90 74 60 90 151 160 90 129 142 152 155 163 171 171 171 214 244 268 259 188 184 171 171 163 154 151 148 162 177 187 155 159 125 107 382.5 373 330 400 441 417 332 321 403 420 455 295.5 294 316 308 327 316 314 313 317 318.5 320 326.5 325 323 329 332 334 346 342 356 358 345 348 357.5 359 404 403 379 386 373 363 362 354 348 349 353 371 371 375 388.5 405 389 388 353 334 336 352 353 362.5 370 388 395.5 395 408.5 430 450 394 387 383 369 367.5 362 350 348 355 367 367 375 376 381 378 380 371 356.5 338 372 398 392 382.5 396 411 424 435 434 430 441 470 468 455 453 425 462 481 462 440 423 435];
y=[359 343 351 377.5 376 383 362 353.5 342 325 301 316 270 292 335 328 335 371 374 394 277 271 265 290 300 301 306 328 337 367 351 355 350 342.5 339 334 335 330 333 330.5 327.5 344 343 346 342 348 372 374 372 382 380.5 377 369 363 353 374 382.5 387 382 388 395 381 375 366 361 362 359 360 355 350 351 347 354 356 364.5 368 370 364 370 372 368 373 376 385 392 392 381 383 385 381.5 380 360 130 118 96 71 70 145 73.5 68 145 138.5 135 114 113 112 117 115 113 118 111 118 109 108.5 105 99.5 102 103 103 100 102 98 96 90 90 96 90 96 96 91 91 71 76 79 81 86 74.5 70 63 63 59 63 69 63 60 57 51.5 65 59 49 40 4

4 33 124 125 139 131 141 140 145 150 145 149 145 131 462 399 400 390 445 409 425 382 444 443 408.5 520 496 465 466.5 462 443 447 422 400 396 401 404 406 404 424 424 423 427.5 431 448 450 459 495 513 528 553 537.5 514 511.5 511 511 497 497 498 451 448 444 434 412 415 425 421 434 451 457 458.5 448 444 446 440 422 419 415 405 403 392.5 387 386 378 376 372 352 350 384 399 397 402 398.5 386.5 389 361 378 396 390 364 370 382 412 413 433 434 400 395 407 414 430 432 441 442 442 435 440 442 442 443 443 444 455 458 460.5 466 464 469 472 477 478 470 494 495 514 514 496 487 486.5 474 457.5 451 451 462 472 481 487 496 507 515 514 507 497 484 466 466 463.5 475 475 484 484 496.5 496.5 507 514 516.5 507 495.5 343 355 377 371 424 442 326 302 240 161 164.5 181 206 242 246 254 254 289 288 246 299 297 287 314 330 360 344 339 337 341 345 345 344.5 350 350 351.5 353 353 359 361 355 370 306 418.5 425 429 433 369 362 366.5 342 340 264 223 210 197.5 173 164 196 168 167 177.5 153 264 285 255 198 15 68 84 149 143 176 160 163 176.5 178 168 177.5 168 164 155 164 168 177 178 188 194 177 177 169 168 167 164 164 153.5 168 133 112 112 141 143 173 170 198 198 199 202 202 201 199 206.5 207.5 206 209.5 212 208 194 222 189 189 187.5 198 196 211 236 244 222 248 265 255.5 258 258 258 252.5 247 235 238 237 255 261 253 263 268 268 268.5 275 274 277.5 281 284 316 292 267 285 267 250 219 247 442 312 246 275 140 269 335 238 244 300 257.5 255 236 230 223 215 222 229 227.5 220 213 212 226 210.5 209 200 202 195 194 188 188 159 161 202 202 213 213 212 218 216.5 215 222 223 224 218.5 219 218 213.5 224.5 233 229.5 232 239 247 236 236 236 237 237.5 233 227 237 268 254 250 250 249.5 249 249 251 255 265 265 257.5 258 260 260 266 270.5 284 281 297 307 308 277 276 270 291 297 319 307 295 309 342 432 361 400 433 437 457 447 449 448 507.5];

q=[1.7 2.1 2.2 1.7 2.1 2.5 2.4 2.4 2.1 1.6 2.6 2.4 2.2 2.5 2.1 2.6 2.5 1.9 1.8 1.9 1.4 1.4 2.4 1.1 1.6 1.2 0.8 1.3 1.4 2.1 1.6 1.5 1.4 1.7 1.4 1.1 0.1 1.2 1.4 1.7 1.4 1.4 1.7 1.1 1.4 1.2 1.6 1.4 1.2 1.1 0.8 0.6 1.4 0.9 1 0.5 0.8 1.1 0.9 0.7 0.6 1.2 1.4 0.8 0.7 0.8 0.8 0.9 1.1 0.9 1.1 0.8 0.9 1.1 0.8 1.1 0.8 0.8 0.8 0.8 1.4 1.1 0.9 1 1.2 1.4 1.1 0.9 1.4 0.9 0.9 0.8 1.6 1.6 1.6 2.1 1.8 1.6 2.6 2.6 1.1 0.9 0.5 0.7 0.4 0.8 0.2 0.8 0.6 0.9 0.8 1.1 0.8 0.4 0.7 1.2 0.8 0.9 0.5 0.6 0.6 0.8 0.9 0.4 0.7 1.1 0.8 0.8 0.7 0.6 0.7 1.2 0.8 1.1 0.8 0.9 1.1 0.6 0.7 0.8 0.4 1.1 0.8 1.1 0.7 0.6 0.8 1.1 0.6 0.4 0.8 0.5 0.1 0.6 0.7 1.1 1.4 1.6 0.8 0.6 0.8 0.6 0.7 1.1 1.1 2.6 2.2 1.4 2.6 2.2 1.9 2.2 2 2.6 2.2 2.1 2.2 1.7 2.2 1.9 2.4 2.4 1.2 1.4 1.2 1.4 0.8 1.2 0.9 0.8 0.8 0.8 0.4 0.9 1.2 1.4 1.4 1.2 1.1 1.2 0.4 0.5 0.8 1.4 0.4 0.8 0.7 0.8 0.7 1.1 1.1 0.8 0.7 0.9 1.2 1.4 1.4 1.6 1.4 1.4 1.2 1.1 0.8 0.9 1.1 0.9 1.1 1.2 0.8 1.4 1.4 1.4 1.1 1.4 1.6 1.2 1.7 1 1.4 1.2 1.4 1.2 1.3 1.2 1.1 1.2 1.1 0.8 1.2 1.5 1.2 1.2 0.7 0.8 1.1 0.9 0.9 1.2 1.2 1.1 0.8 1.1 0.9 0.5 1.2 1.6 1.4 1.2 0.9 1.4 1.6 1.7 2.1 1.4 1.2 1.5 1.2 1.1 0.8 0.7 1.1 0.8 0.4 1.4 1.4 0.8 0.7 0.7 0.8 0.8 1.2 1.4 1.6 1.4 1.2 1.6 1.

4 1 1.2 0.8 1.2 0.7 1.2 1.3 1.4 1.4 1.4 1.5 0.8 0.7 0.9 0.6 0.8 0.7 0.9 0.8 0.6 1.1 1.4 2.4 1.7 2.5 2.4 2.1 2.2 2.6 2.1 2.6 0.4 0.1 0.6 0.2 1.4 1.6 1.1 1.2 0.7 1.1 0.7 1.4 1.6 1.4 1.7 1.1 1.2 0.8 2.4 1.2 1.1 1.6 0.8 0.8 0.4 0.7 1.1 1.4 0.9 1.1 0.9 0.8 0.6 0.1 1.4 1.4 1.6 1.4 1.9 1.4 1.2 1.2 1.5 2.4 1.9 2.4 2.6 2.6 2.6 2.6 2.4 1 1.1 1.9 2.6 2.4 2.4 1.7 1.1 0.8 0.2 1.6 0.9 1.4 0.6 0.7 0.7 0.8 0.6 0.8 0.7 0.6 0.7 0.9 1.2 0.9 0.9 1.5 1.7 0.8 1.1 0.8 0.8 0.9 0.2 0.7 1.2 1.6 1.6 1.1 1.4 1.6 1.7 1.4 1.9 0.4 0.3 0.6 0.4 0.4 1.1 0.1 0.6 0.5 0.2 0.4 0.1 0.4 1.1 1.6 0.8 0.9 0.6 0.7 0.4 1.6 1.4 1.5 0.8 1.7 2.1 1.1 0.6 0.8 1.1 0.4 1.2 1.1 1.1 1.1 1.1 1.4 1.2 1.1 0.8 0.9 0.7 0.4 1.5 1.5 0.7 1.4 1.6 1.8 1.8 1.6 2.4 1.9 0.8 2.3 1.7 1.5 1.9 1.7 2.1 2.4 1.9 1.4 1.1 1.5 1.2 0.8 1.4 0.9 0.6 0.2 0.3 0.5 0.7 0.6 0.4 0.7 0.7 0.6 0.7 0.8 0.7 0.6 0.4 0.4 0.6 1.1 1.2 0.8 0.7 0.8 0.6 0.4 0.8 0.6 0.9 0.7 0.8 0.8 0.6 0.4 1.1 0.8 0.9 0.6 0.8 0.7 1.1 1.2 0.6 0.8 1.1 1.2 1.4 1.1 1.5 1.4 0.1 1.4 0.9 1.1 0.8 0.7 0.8 0.6 1.4 1.1 0.8 1.2 1.4 1.1 1.7 1.4 1.2 1.1 1.4 1.2 1.4 1.5 1.1 0.9 1.4 1.2 0.8 0.9 0.7 1.4 1.2 0.2 1.2 0.6 0.6 0.8 1.4 0.6 1.2 1.4 1 0.4];
xx=[1 1 2 3 3 4 4 5 5 6 7 7 8 8 9 10 11 11 12 12 14 15 15 16 16 17 17 17 18 18 19 20 21 22 22 23 23 24 24 25 26 26 27 28 28 29 30 30 31 31 32 33 33 34 35 36 36 36 36 37 38 38 39 40 41 41 42 43 43 44 45 46 46 47 47 47 48 49 49 50 51 51 52 53 53 54 54 55 56 57 57 57 58 60 61 62 62 63 64 64 65 66 66 67 67 68 68 69 69 69 70 70 71 71 72 73 73 74 74 75 76 77 77 78 79 80 81 82 82 83 84 85 86 86 87 87 88 88 89 89 89 90 91 93 94 95 95 96 96 96 97 97 98 99 100 100 101 102 102 103 103 104 105 105 106 106 107 108 108 108 108 109 110 111 111 112 113 113 114 114 115 115 116 116 117 117 118 118 118 119 120 120 121 121 122 122 123 123 124 124 125 126 126 127 127 128 128 129 130 130 131 132 133 133 134 134 135 135 136 137 138 139 139 140 141 142 142 143 144 144 145 146 147 147 148 149 150 150 151 152 154 155 155 156 157 157 158 158 158 159 160 160 161 162 163 164 165 166 166 167 167 168 170 170 171 171 171 172 173 173 173 174 174 175 175 176 176 177 178 178 179 179 180 180 180 180 181 182 183 183 184 185 186 187 187 188 188 189 189 190 190 191 192 194 194 195 195 195 196 196 198 198 199 200 201 201 203 203 204 204 205 205 206 207 207 208 209 209 210 210 211 212 213 215 215 216 216 218 218 219 219 220 221 221 221 222 222 222 223 224 225 225 226 226 227 227 228 229 229 230 231 232 233 234 235 235 235 236 237 237 237 238 239 239 240 241 242 243 243 244 245 245 245 246 246 246 246 247 247 248 248 248 249 250 250 251 252 253 253 254 255 256 258 258 259 259 259 261 261 262 262 263 263 265 266 266 266 267 267 268 269 270 270 271 271 271 272 273 273 274 274 275 276 276 277 277 278 279 279 280 280 281 282 284 285 285 286 286 286 286 287 288 289 289 290 290 291 291 292 292 293 293 294 294 294 295 295 296 296 297 298 298 299 299 300 300 301 302 302 303 303 304 305 306 307 308 308 308 309 309 310 310 311 312 312 313 314 314 315 315 315 316 317 317 317 317 31

8 318 319 319 320 321 321 321 322 323 324 324 326 327 329 329 331 332 333 333 333 334 334 335 336 336 337 337 338 338 338 339 340 341 341 343 343 344 345 345 346 346 346 347 347 348 348 349 349 350 350 351 351 352 353 353 354 354 355 356 356 357 357 358 359 359 360 361 361 361 361 362 363 363 364 365 365 366 367 368 368 369 370 370 371 372 373 373 373 374 375 375 375 376 377 377 377 378 379 380 381 381 382 382 382 383 384 384 385 385 386 386 387 387 388 388 388 389 389 390 390 392 392 392 393 393 394 394 395 395 396 396 396 397 398 399 399 400 400 401 402 402 403 403 404 404 404 405 406 407 407 408 408 409 410 411 412 412 413 414 415 415 415 416 417 417 418 419 420 420 421 422 423 423 423 424 424 425 425 426 427 427 427 428 428 429 429 431 432 432 432 434 435 437 438 439 439 440 440 441 442 444 444 445 446 447 447 448 448 449 449 450 450 451 451 452 453 453 454 454 455 456 456 457 457 457 458 458 459 459 460 460 462 463 464 465 466 466 468 468 469 469 470 470 471 472 472 474 474 474 474 475 475 476 477 478 478 479 479 480 482 482 484 484 485 485 485 486 486 487 488 488 489 489 490 490 491 491 491 492 492 493 493 494 494 495 496 496 497 497 498 498 499 500 500 501 501 502 502 504 505 505 506 506 507 508 508 508 509 510 511 511 512 513 514 515 516 517 517 518 518 518 519 519 520 521 521 522 522 523 524 524 525 525 526 527 528 528 528 528 529 530 531 531 532 532 532 533 533 534 535 536 537 537 538 539 539 539 540 540 542 542 543 543 544 544 545 545 546 546 547 548 548 549 549 550 550 551 551 552 553 553 554 556 556 557 557 557 558 560 560 560 561 561 561 562 562 563 563 565 566 567 567 568 568 569 569 570 572 572 573 574 575 576 577 577 580 580 581 581 581 582];
yy=[75 78 44 45 65 39 63 49 50 59 32 47 9 47 35 34 22 26 25 471 21 7 31 14 38 40 42 81 81 83 79 86 22 372 13 13 383 13 25 11 27 10 12 29 15 30 7 48 32 34 33 34 8 9 45 35 37 16 39 7 39 41 40 2 17 92 43 2 72 3 46 8 55 48 6 5 61 50 53 51 52 59 56 52 54 55 63 3 57 58 60 4 59 62 60 4 85 64 65 76 66 67 76 44 68 69 75 70 71 1 2 43 72 74 73 74 18 1 80 76 77 78 19 79 80 18 82 83 90 84 85 20 87 88 88 92 89 91 20 84 90 91 92 104 110 116 136 137 138 142 99 143 165 148 132 150 102 103 156 93 154 105 106 107 111 117 94 94 107 106 109 110 112 109 113 113 114 116 115 154 95 165 117 129 118 128 105 119 126 120 121 123 104 122 123 125 124 126 125 127 132 127 128 130 133 129 130 131 131 134 135 133 134 140 135 96 136 137 99 97 139 140 142 141 146 143 145 144 145 148 146 147 149 150 149 152 151 152 152 153 155 156 157 159 158 164 159 162 164 160 161 162 163 163 164 98 377 265 181 250 255 189 225 227 228 216 231 219 233 232 236 213 220 197 196 184 187 582 210 284 291 274 305 270 306 307 308 273 184 196 185 186 168 185 186 176 186 190 192 62 191 192 193 193 175 194 188 196 197 198 177 199 200 201 177 202 202 204 205 178 206 210 207 200 208 199 206 208 209 211 212 213 214 214 175 215 217 217 172 214 174 212 211 220 222 220 178 223 224 174 223 226 224 172 172 228 218 228 230 171 232 233 234 168 234 48 173 237 30 2

35 238 239 29 240 241 242 243 230 244 231 244 232 236 241 242 245 247 237 238 369 239 249 167 251 252 252 253 240 254 169 256 257 249 260 258 248 260 260 262 263 267 261 264 262 181 265 267 255 268 269 270 257 271 256 272 295 182 170 241 273 275 276 170 277 278 283 275 278 280 277 281 282 283 282 284 281 285 204 203 287 288 285 288 290 285 291 281 279 179 293 182 274 292 293 272 292 296 179 290 296 289 297 298 288 299 301 287 301 303 300 304 299 304 297 269 307 268 309 310 312 307 311 305 311 313 314 311 304 303 314 316 302 264 203 316 318 315 319 181 313 350 356 358 368 367 363 364 365 347 343 330 331 392 330 331 334 339 328 335 336 333 337 338 343 339 342 327 447 341 342 327 344 326 345 346 323 326 352 360 348 320 340 349 320 371 351 355 352 354 353 354 357 355 356 321 357 358 358 360 359 360 367 361 362 323 322 264 332 325 324 367 364 366 369 368 349 369 370 371 29 28 23 431 438 456 436 424 429 430 375 416 417 376 458 423 397 399 405 402 101 93 460 467 473 449 473 442 444 388 390 389 391 100 330 153 391 329 393 395 439 391 394 395 380 396 440 380 398 441 398 381 400 403 401 402 382 403 414 404 410 405 407 408 406 407 437 438 409 410 411 411 412 413 416 414 415 101 161 416 437 418 421 419 420 421 422 379 379 376 424 378 425 429 426 428 427 378 428 436 429 433 431 432 434 433 434 374 435 374 373 446 440 443 441 442 386 443 445 332 446 455 444 448 445 385 450 467 446 451 452 465 453 454 462 455 461 456 457 372 374 458 372 459 486 14 21 461 462 463 464 452 466 467 468 464 469 463 470 383 24 472 468 384 447 473 471 340 555 565 545 501 542 566 577 580 568 489 559 539 570 571 572 573 487 491 488 482 560 487 490 481 550 481 492 530 493 496 494 495 495 499 498 495 497 498 501 499 477 500 477 502 520 530 503 504 505 506 513 507 509 504 507 509 510 510 511 512 483 513 514 515 516 517 518 523 505 519 521 503 520 521 522 529 523 527 524 515 525 514 526 512 525 527 529 536 538 530 531 481 532 533 547 548 529 534 535 536 537 538 478 539 526 540 478 541 484 543 565 536 544 476 555 535 546 547 552 534 549 552 481 550 551 559 552 556 553 476 554 555 554 475 475 558 564 559 549 16 561 38 558 562 563 480 564 565 566 567 480 569 569 574 570 571 571 541 578 578 575 576 479 573 579 579 581 576 582 183 578];

for i=1:length(xx)
if xx(i)<93 & yy(i)<93 % && xx(i)>0 && yy(i)>0
xxa(i)=xx(i);
yya(i)=yy(i);
end
end

for i=1:length(xxa)
if xxa(i)==0
xxa(i)=12;
end
if yya(i)==0
yya(i)=20;
end
end


%A area
xa=x(1:92);ya=y(1:92);qa=q(1:92);
%B area
xb=x(93:165);yb=y(93:165);qb=q(93:165);
%C area
xc=x(166:319);yc=y(166:319);qc=q(166:319);
%D area
xd=x(320:371);yd=y(320:371);qd=q(320:371);
%E area
xe=x(372:474);ye=y(372:474);qe=q(372:474);
%F area
xf=x(475:582);yf=y(475:582);qf=q(475:582);


%随机产生邻接矩阵
aa=10^8*ones(length(xa));

%计算边权
for k=1:length(xxa)
i=xxa(k);j=yya(k);
aa(i,j)=100*sqrt((xa(i)-xa(j))^2+(ya(i)-ya(

j))^2);
end

for i=1:length(xa)
for j=1:length(xa)
if i>j && aa(i,j)<10^8-10
aa(j,i)=aa(i,j);
end
end
end

%对称化距离矩阵
for i=1:length(xa)
for j=1:i
if i==j
aa(i,j)=0;
else
aa(i,j)=aa(j,i);
end
end
end

%佛罗伊德算法，d2距离矩阵，r2路由矩阵
[dda,rra]=floyd(aa);

%绘图
figure();
%画节点
%for i=1:length(xa)
% plot(xa(i),ya(i),'.');
% hold on;
%end
for i=1:92
plot(xa(i),ya(i),'r.');
hold on;
end
%画标识
for i=1:92
ii=num2str(i);
text(xa(i)+2,ya(i)+2,ii);
hold on;
end
%画道路
for i=1:size(xa,2)
for j=i:size(xa,2)

if aa(i,j)<=10^8-10;
plot([xa(i) xa(j)],[ya(i) ya(j)]) ;
hold on;
end
end
end



vva=zeros(92,20);
for i=1:92
for j=1:20
if dda(i,j)<3000
vva(i,j)=1;
end
end
end

sumvva=sum(vva,2);
for i=1:92
if sumvva(i)==0
[minvva,minvvanum]=min(vva(i,:));
vva(i,minvvanum)=1;
end
end
sumvva=sum(vva,2);

%遗传算法

N=101;%种群数量,最后一个保留最优个体
runnum=200;%遗传算法次数

w0=rand(92,N); %随机产生初始种群
for i=1;92
w1=ceil(w0*sumvva(i));
end


valuef=zeros(1,N);%记录每一次的最优适应度函数值


vvva=zeros(92,20);

%让非零元素排在前
for i=1:92
[maxvva,maxvvanum]=sort(vva(i,:));
vvva(i,1:sumvva(i))=maxvvanum(21-sumvva(i):20);
end

for j=1:runnum
%valuef=hanshu(w1,dda,vvva,q);%sizex的取值x0表示对原来的节点的覆盖，x表示对扩展的节点的覆盖
w1=jiaocha(w1);%交叉
w1=bianyi(w1,sumvva);%变异
valuef=hanshu(w1,dda,vvva,q);%计算适应度
[valuezhi,valuenum]=max(valuef);
w1(:,N)=w1(:,valuenum);%保留最优个体
w1=xuanzhelinear(valuef,w1,N,0,1);%选择
w2(:,j)=w1(:,N);
end

maxvaluef=hanshu(w2,dda,vvva,q);


figure()
plot(maxvaluef);