Starting theme version 4.20, the categories fields will support a multi-selection option in the Advanced search form.  The option for this functionality can be found in Theme Options-Search-Taxonomies Multi-Selection.

The multi-selection option will work only if the option Custom Fields For Advanced Search? is set to Yes