Firm-heading forms had become well developed in Europe by the 16th century, but when they first were developed is unknown. The oak-leaved and curled-leaf types, and various colors now known, were all described in the 16th and 17th centuries in Europe.
(from some site)
I'm not nitpicking, but I believe heading lettuce would be a bad place to look for "evolutionary traits". I don't think heading lettuce could make it in the wild. This is a plant developed (manipulated?) by man to suit a purpose not related to direct competition. I would not be surprised if the inside leaves are just blanched and waiting to be eaten. The only function is to attract you so that you will propagate it. Kind of like the flowers of MJ will be in 1000 years.
Brassica Oleracea as a species includes cabbage, brusseld sprouts, broccoli, kohlrabi, kale, collards, and broccoli, none of who have traits evolved via natural selection (unless you take the view that we are being manipulated as much as they are).